这是我算出来的上面那个模式串1～14的next[] ，有没有算对呀？

Question

大家帮我解决下这个问题，可以不？
求这个模式串的next函数
'abaaabcabcbcac'

我自己是算出来了，但又不敢肯定结果，大家帮我看下，好不？

我算出来的是：
0,1,1,
2,2,2,
4,3,2,
7,3,5,
3,2.

Answer 1

下标从1开始, next[i]表示已匹配上i个字符, 第i+1个字符不匹配, 余下部分所能匹配的最长前缀next[1-14] = {0, 0, 1, 1, 1, 2, 0, 1, 2, 0, 0, 0, 1, 0}参考程序, pat为字符串指针, 首字母位于pat[1], p[]即为你所述的next[]void compute_next(char *pat){p[1] = 0;int j = 0;for(int i = 2; pat[i]; ++i){while(j > 0 && pat[j + 1] != pat[i]) j = p[j];if(pat[j + 1] == pat[i]) j += 1;p[i] = j;}}