大家幫我解決下這個問題，可以不？求這個模式串的next函數'abaaabcabcbcac'我自己是算出來了，但又不敢肯定結果，大家幫我看下，好不？我算出來的是：0,1,1,2,2,2,4,3,2,7,3,5,3,2.
1 回答
慕后森
TA貢獻1802條經驗 獲得超5個贊
下標從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;
}
}
- 1 回答
- 0 關注
- 96 瀏覽
添加回答
舉報
0/150
提交
取消