KMP算法的next函数怎么计算

计软刷题时刷到一个题目，模式串p为“abaac”，求其next函数。代码就不解析了（我也没咋看），为了应试总结了一个快速答题技巧

首先，按位序、模式串、next函数写下来：

位序 1 2 3 4 5 模式串 a b a a c next值 第一步：next值的前两位是0和1，代码是这样初始化的，记住就行了

位序 1 2 3 4 5 模式串 a b a a c next值 0 1 第二步：计算next第3位，即next[3]的值

位序 1 2 3 4 5 模式串 a b a a c next值 0 1

当前计算结果=1 比较基准：用前一位的模式串进行比较，记作模式串[2]吧，模式串[2] = b, 即比较基准为‘b’。

比较对象：与什么比较呢，前一位next值所对应的位序上的字符进行比较，因为next[2] = 1，所以与位序1上的字符即模式串[1] = a比较。将b与a进行比较。

计算结果：如果不相等，结果为1；如果相等，在前一位next值上+1。比较到模式串第一个字符为止。这里已经比较到第一个模式串字符了，而且b！=a，所以结果为1.

第三步：计算next第4位，即next[4]的值

位序 1 2 3 4 5 模式串 a b a a c next值 0 1 1

当前计算结果=2 比较基准：用前一位的模式串进行比较，即模式串[3] = a, 即比较基准为‘a’。

比较对象：与什么比较呢，前一位next值所对应的位序上的字符进行比较，即与next[3] = 1位序上的字符比较，即模式串[1] = a。将a与a进行比较。

计算结果：如果不相等，结果为1；如果相等，在前一位next值+1。比较到模式串第一个字符为止。这里已经比较到第一个模式串字符了，而且a=a，所以结果为next[3]+1 = 1+1 = 2.

第四步：计算next第5位，即next[5]的值

位序 1 2 3 4 5 模式串 a b a a c next值 0 1 1 2 当前计算结果=2

比较基准：用前一位的模式串进行比较，即模式串[4] = a, 即比较基准为‘a’。

比较对象：

与前一位next值所对应的位序上的字符进行比较，即与next[4] = 2位序上的字符比较，即模式串[2] = b。将a与b进行比较，不相等，当前结果初始化为1。

因为没有比较到第1位的字符串，接着比较：与位序为next[2] = 1的字符比较，即模式串[1]=a。将a与a比较，相等，当前结果+1，即结果为1+1 = 2. 因为已经比较到第一位字符串了，所以比较结束。

最终，next值为01122.

总结一下，就是next的最开始两位为01.接下来每一位的值，都是用前面的一位模式串值去比较，一直比较到模式串的第一位为止。如果相等，当前结果为前一位的next值+1，如果不等，则初始化为1.