数据结构模式匹配求next值

Question

主串abcaabccacabcabcaaaabc，模式abcabcaaa，怎么求next值，详细通俗点的过程，我记得以前做的时候基本不用计算一眼就能看出来，放下一年多再拿起来怎么想也想不起来了，麻烦谁跟我说下，是只看模式串还是同时要看主串？具体怎么求？要最简单方便的那种

Answer 1

看模式串'abcabcaaa'第1个没疑问next[1]=0，第2个字符b前一个字符为a，a前面没字符了，所以next[2]=0+1=1，第3个字符c,前面一个字符为b，b前面没有和他匹配的，那么next[3]=0+1=1，第4个a，前面个字符为c，c前面没有匹配字符，那么next[4]=0+1=1,第5个b，前面一个字符a有匹配的，长度为1，next[5]=1+1=2，第6个c,前面字符ab(长度为2)有匹配的,那么next[5]=2+1，以此类推得next[7]=4,next[8]=5,next[9]=2.

参考资料：ogin_u

Answer 2

只看模式串就可以了，比如
abcabcaaa，在第四个a发现不匹配的时候，由于前面是abca，这个与最开头的4个字符是相同的，所以直接判断与第五个字符是不是相同的，也就是是不是b。

Answer 3

寻找重复串就可以了吧，我算出来是—1 0 0 0 1 2 3 4 1