考研中关于计算KMP算法中的next数组和nextval数组

考研中KMP算法中，如何手动求next数组和nextval数组？

首先我们要理解next数组的意义，为了实现更加高效的字符匹配，next数组是用来寻找字符串数组内部的自身的一种规律，利用字符串内部的一种相似性，来优化字符串数组匹配算法。所以才需要计算这么一个next数组来帮助算法更好的实现字符串匹配。

next数组的计算方式逻辑上稍微复杂，初学者可能很难看懂，所以首先要理解，为什么要计算next数组以及更加优化的nextval数组。假如有这样一串字符串123456aaaaaa这可以说是一个字符串间规律最强的一个数组了吧，让我们来手动模拟一下。

首先默认第一位是0，第二位是1，从第3位开始求，比较第3-1位和next[3-1]的字符是否相同，若相同，则next[3]=next[2]1所以第3位的值就是2.那么依此类推就可以得到，这个字符串的next数组为123456aaaaaa012345总结来看就是相同就在他的next数组值加1.那么有这样一个字符串那123456abcdef默认给出第1位为0第二位为1，发现全都不一样,可以说毫无相关性了，所以next数组为123456abcdef011111

这两种极端情况可以让大家初步了解一下计算next数组的方法，起码可以初步理解一下next数组的意义。但是这还不完善。下面介绍一到北邮2016年考研真题12345678abaabcac01122312这是一个考试常见的字符串，是如何计算的那？

第n位：next[n]的值来自于第n-1位的字符，通过跟第next[n-1]位字符比较，如果相同next[n]=next[n-1],如果不相同，就跟第next[next[n-1]]位的字符比较，就这样迭代直到相同的时候，加上1，如果实在没有，就为1.这一段话可能很难理解，逐位分析。让我们从依次来看：第3位：第2位和第1位比较，不相同所以为1第4位：第3位和第1位比较，相同，所以为2第5位：第4位和第2位比较，不相同，和第1位比较，相同，所以为2第6位：第5位和第2位比较，相同，所以为3第7位：第6位和第3位比较，不同，和第1位比较，不同，所以为1第8位：第7位和第1位比较，相同，所以为2.这就是next数组的手动计算方法。

接下来介绍如何根据next数组计算nextval数组nextval是在next数组的基础上优化算法，避免不必要的浪费。其实我也不太理解nextval的具体原理，现只能介绍一下如何计算。依旧用上面北邮的真题为例，其真题本身求的就是nextval数组现在我们已经有了next数组：12345678abaabcac01122312现在通过next数组计算nextval数组，nextval数组与next相反，是找不同，12345678abaabcac0112231201021302第1位：必为0第2位：第2位next值为1，所以第2位和第1位比较，不同，为第2位的next值1第3位：第3位next值为1，所以第3位和第1位比较，相同，因为到第1位了，所以为0第4位：第4位next值为2，所以第4位和第2位比较，不同，就为第4位next值2第5位：第5位next值为2，所以第5位和第2位比较，相同，则继续，第2位和第1位不同，则为第2位的next值1第6位：第6位next值为3，所以第6位和第3位比较，不同，就为第6位的next值3第7位：第7位next值为1，所以第7位和第1位比较，相同，则为0第8位：第8位next值为2，所以第8位和第2位比较，不同，则为第8位的next值2

【简而言之】第n位nextval数组值就是，让第n位字符和第next[n]位比较，不同，则nextval[n]=next[n],如果相同，则比较第next[next[n]]位和第next[n]位比较，如果不同，则nextVal[n]=next[next[n]].就是这样的计算方式。