如何求字符串next数组值

求字符串next数组值：

已知String str = "aaab"其Next数组值结果为  0123。

已知或敬String str = "babab"其Next数组值结果为  01123。

计算过程：

计算3b （3b表示坐标为3的b）：先比较3b的前一位2a，2a的NEXT值为1，将2a和坐标为1的串1b比较，不相等，因为1b是第一位，所以最终3b的NEXT值为1。

计算4a：先比较4a的前一位3b，3b的NEXT值为1，将3b和坐标为1的串1b比较，相等，所源颂以最终4a的NEXT值为（3b的NEXT值 + 1）= 2。

计算5b：同理计算4a，可得计算结果为2+1=3。雹团郑

扩展资料

next的优点

KMP算法优于简单字符串匹配算法的根本原因就是：引入了一个next数组，这个数组可以尽可能的记录相关的匹配信息，使得在不匹配发生的时候移动的步长不再是固定的一位，加快了匹配进行的速度。

在失配后，并不简单地从目标串下一个字符开始新一轮的检测，而是依据在检测之前得到的有用信息即next数组中记录的信息，直接跳过不必要的检测，从而达到一个较高的检测效率，关于它的讲解、实现和优化网上。

参考资料来源：百度百科—kmp算法

next数组的求解方法： 首先第一位的next值直接给0，第二位的next值直接给1，后面求解每一位的next值时，都要前一位进行比较。首先将前一位与其next值的对应位进行比较，若相等，则该位的next值就是前一位的next值加上1；若不等，继续重复这个过程，直到找到相等某一位，将其next值加1即可，如果找到第一位都没有找到，那么该位的next值即为1。

举例：

另解（不想看可跳过）：

求next数组：

先求模式串S 每一个字符前面的那个字符串的最大公共前后缀长度，将这一系列长度存成一个数组，求出来的每个长度其实就是和模式串每一个对应位置上做比较的下标

例如：模式串是 ABACABC ，其最长公共前后缀长度数组为：我们将最长公共前后缀长度记作 LCPSF ，现在从模式串第一个字符A开始，A的前面字符串为null，所以A之前的子串的 LCPSF 是0；来到B，B的前面字符串是A，A是单独的字符不存在公共前后缀，所以长度也是0；来到A，A前面的子串是AB， LCPSF 为0；来到C，C前面的子串是ABA， LCPSF 为1；来到A，A前面的子串是ABAC， LCPSF 为0；来到B，B之前子串为ABACA， LCPSF 为1；来到C，C前面子串为ABACAB， LCPSF 为2；到此这个最长公共前后缀数组就出来了 [0,0,0,1,0,1,2] 将这个数组从第二个值开始每个值加1后，得到 [0,1,1,2,1,2,3] 就是将要和子串对应位置比较的下标，即为next数组。

掌握了上面求next数组的方法后，我们可以迅速求得模式串ABACABC的next数组为[0,1,1,2,1,2,3]，现在继续求模式串ABACABC的next-val数组：

求解nextval数组是基于next数组的，模式串每一个位置的字符和其next数组值给出的下标的对应位置的数作比较，相等就取next-val中对应的next数组值作为当前位置字符的next-val值，不等就直接取当前位置字符的next数组的值作为next-val的值。

求解步骤：

next-val数组第一个数直接为0。

next-val第二数：模式串第二个字符为B，对应的下标数组第二个数是1，那就是将模式串的第1个字符和B相比较，A!=B,所以直接将下标汪族数组第二个数1作为next-val数组第二个数的值

第三个数：模式串第三个字符为A，对应下标数组第三个数为1，取其作为下标，找到模式串第1个字符为A，A=A，那取next-val的第一个数做为next-val第三个数的值，也就是0

举例：

next数组的缺陷举例如下：

比如主串是"aabXXXXXXXXXXXXXX"，模式串"aac"

通过计算 "aac" 的next数组为012，当模桐陵带式串在字符c上失配时，会跳到第2个字符，然后再和主串当前失配的字符重新比较，即此处用模式串的第二个a和主串的b比较，即 "aabXXXXXXXXXXXXXX"vs"aac"，显然a也不等于b。然后会跳到1接着比，直到匹配成功或者匹配失败主串后移一位。

而"aac"的nextval数组为002 当在c失配时会跳到2，若还失配就直接跳到0，比next数组少比较了1次。

在如果模式串很长的话，那可以省去很多比较，因此使用nextval数组比next数组高效。

在模式匹配的KMP算法中，求模式的next数组值（也称为KMP算法中失败函数）定义如下：

（1）当j=1时，为什么要取next[1]=0?

答：局芦当模式串第一个字符与主串中某字符不匹配时，主串指针应移至下一字符，再和模式串第一个字符比较。（next[1]=0 表示模式串中已没有字符可与主串中当前字符 s[i] 比较）

（2）为什么要取 max{k}，k最大是多少？

答：当主串中第 i 个字符与模式串中第 j 个字符不匹配时，若主串 i 不回溯，则假定模式串中第 k 个字符与主串中第 i 个字符比较，k 值应满足条件 1<k<j，并且 'p1...pk-1' == 'pj-k+1...pj-1'，即模式串向后移动的距离为 k，k值可能有多个，为了不使移动产生丢失可能的匹配，k要取最大值，max{k}表示移动的最大的距离，k的最大值为 j-1。

（3）其它情况是什么？为什么取 next[j] = 1?

答：以上两种情况的不匹配，主串指针不回溯，在最坏的情况下，模式串从第 1 个字符开始与主串第 i 个字符比较，以便不丢失可能的匹配。

---