正題

題目鏈接：
http://poj.org/problem?id=2752

---

大意

一個字符串，求所有的前綴等于后綴的長度

---

解題思路

用KMP求出Next數組。然后最大的那個肯定是長度，然后讓j=l，之后每次j=next[j]，直到j<0。

這里講解一下原理，首先第一次next[l]是可以理解的因為next[i]表示的就是除了n外最大的前綴等于后綴長度。之后繼續往前跳的原理是：
這里拿樣例當一下：
ababcabab①|ababcabab②
因為①已經等于②了，所以①的后綴就等于②的后綴，然后②的后綴就是原串中長度為next[l]的后綴，然后這里的next就是求長度小于next[l]的前綴等于后綴的，然后以此類推。

---

代碼

#include<cstdio> #include<cstring> using namespace std; char s[400001]; int l,p[400001],ans[400001],tot; void ycl() {p[0]=-1;tot=0;for (int i=1,j=-1;i<=l;i++){while (j>=0&&s[i]!=s[j+1]) j=p[j];if (s[i]==s[j+1]) j++;p[i]=j;}//KMP匹配int j=l-1;while (1){j=p[j];//往后跳if (j<0) break;ans[++tot]=j+1;//記錄}while (tot){printf("%d ",ans[tot]);//輸出tot--;}printf("%d",l); } int main() {while (scanf("%s",s)!=EOF){l=strlen(s);ycl();printf("\n");} }

總結

以上是生活随笔為你收集整理的POJ2752-Seek the Name, Seek the Fame【KMP】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。