題意：給你一串字符串，問你前后綴相同情況有幾種，并輸出后綴位置（？這里一直沒看懂length是什么，但是這樣理解答案也對，然后還要加上本身長度）

思路：這里好好講講next的用法。我們都知道next代表前后綴匹配值，現(xiàn)在我們以下面這個字符串為例，講述next的用法：

len = 9,next[len] = 4，所我們找到了第一個前后綴匹配串a(chǎn)bab，next[ next[len] ] = next[4] = 2，所以第二個前后綴匹配串長度為2。因為next[len] = 4，所以s[0...3] == s[5...8]，而next[4] = 2，即s[01] == s[23] == s[89]，所以第二個前后綴匹配串為ab。以此類推，直到next<=0。

參考

代碼：

#include<set> #include<iostream> #include<algorithm> const int maxn = 1000000+5; const int INF = 0x3f3f3f3f; using namespace std; int fail[maxn],ans[maxn]; char s[maxn]; void getFail(char *p,int len){fail[0] = -1;int j = 0,k = -1;//int len = strlen(p);while(j < len){if(k == -1 || p[j] == p[k]){fail[++j] = ++k;}else{k = fail[k];}} }int main(){int T,Case = 1;scanf("%d",&T);while(T--){scanf("%s",s);int len = strlen(s);getFail(s,len);int i = len,cnt = 0;while(fail[i] > 0){ans[cnt++] = len - fail[i];i = fail[i];}ans[cnt++] = len;sort(ans,ans+cnt);printf("Case #%d: %d\n",Case++,cnt);for(int i = 0;i < cnt;i++){if(i != 0) printf(" ");printf("%d",ans[i]);}printf("\n");}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/KirinSB/p/9408762.html

總結(jié)

以上是生活随笔為你收集整理的FZU 1901 Period II（KMP中的next）题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。