已知串S=‘aaab’,其Next数组值为（ ）

答案A

序号：1 2 3 4

数组：a a a b

next： 0 1 2 3

注意上边序号、数组和next的对应关系

求next值的过程：

前两位：next数组值前两位一定为01，即aaab中的前两位aa对应01，如上表中next第1，2位为0和1其实这就可以选出答案了

第三位：3a前面是2a（2a表示序号为2的a），2a的next数组值为1，找到序号为1的字符, 即1a,将2a和1a相比，两者相同，都是a，则3a的next值为2a的next值加1，即2；

第四位：4b前3a的next为2，找到序号为2的字符, 即2a, 将3a与2a相比，二者相同，则其next值为3a的next加1，为3

结果为0123，选A

如果比较的时候碰到与前一位字符“不同”怎么办？如求下列序号4的next值

序号: 1 2 3 4

数组: a a b a

next: 0 1 2 1

以前一位的next值为序号，找到这个序号对应的字符，再进行比较，4a前一位是3b, next值为2, 找到序号2对应的2a, 比较3b和2a, 两者不同, 再重复这一步骤, 找到2a的next值是1，比较3b和1a, 不同, 那么所求的4a的next就是1, 如果相同就是2a的next值加1，为2。

做个练习：xyxyyxxyx,求它的next数组？

答案是011231223，你做对了吗？

求字符串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算法