这是我算出来的上面那个模式串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;
}
}