数据结构KMP模式匹配算法的next[j]为什么是下面写的那样

Question

想问下数据结构KMP模式匹配算法的next[j]为什么是下面写的那样
j 1 2 3 4 5 6 7 8
模式串a b a a b c a c
next[j] 0 1 1 2 2 3 1 2
以上是一一对应
有解释说是相等加1，不相等向前找，首位置不等1，我理解是前一个位置和首位置比较相不相等，不知道是不是
如果是的话，为什么第5个位置的前一个位置不是和首位置一样吗？那不是应该加一吗？那不就是3

Answer 1

你的理解有点偏差，设模式串为string[i],求next[j]不是前面一个相等就加一，而是要看前面紧接的子串有多少个相等，j=4时紧接的子串只有string[3]==string[1],故next[j] =2，同理j=5时也只有string[4]==string[1]，故next[j] =2。如果要next[5]=3,必须要满足string[3]==string[1]并且string[4]==string[2]的条件。
你看的是不是清华大学那本数据结构呢，有点说的不清不楚的。那个求next数组的算法多看几遍就可明白了。追问

你那是观察法，我讲得是另一种方法，我是想问另一种方法是什么东西相等加一

追答

求next数组最简单就是这种方法了，又何来另一种方法？
由定义，next[1]肯定是0
设next[j]=k,就会有，（1<k<j）
string[1]····string[k-1]==string[j-k+1]····string[j-1]
在前面基础上，如果string[k]==string[j]，就有next[j+1] = next[j]+1（注意了，这里相等加一）
还有一种情况string[k]不等string[j]，将模式串滑动到next[j]处与string[j]比较，原理一样的,我就不细说了.
代码写起来也很简短，自己去搜下吧。

追问

问下可以说下你的Q号码？可能以后有问题想问你

Answer 2

不等就往前找啊！追问

为什么第5个位置的前一个位置不是和首位置一样吗？那不是应该加一吗？那不就是3