版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。

Power Strings Time Limit:?3000MS ? Memory Limit:?65536K Total Submissions:?24403 ? Accepted:?10264 Description 給你一個字符串a(chǎn)，問a最多由幾個完全相同的子串連接而成 Input 每一個測試點都會給你一個長度為m（1<=m<=1000000)的字符串，并以句號結(jié)尾。 Output 輸出a最多由幾個完全相同的子串連接而成。 Sample Input abcd aaaa ababab . Sample Output 1 4 3 Hint 用cin會超時 next[j]的值代表當前的模式串 j位置之前的字符 最大的相同的前綴后綴， 也意味著當前綴后綴不匹配時 模式串j位置要和模式串next[j]位置的字符來匹配，則模式串第1位到next[j]與模式串第j-next[j]位到j(luò)位是匹配的。更意味著前綴后綴匹配失敗時 模式串要向后移動j-next[j]個位置，這個題就是考察的j-next[j]是不是j的倍數(shù) 當存在長度為n的字符串要是由長度為m的循環(huán)節(jié)組成那么循環(huán)節(jié)的個數(shù)一定是n/m,而現(xiàn)在循環(huán)判斷到模式串最后一個字符n-1（因為數(shù)組下標用的是從0開始）位置時，(循環(huán)體內(nèi)會得到數(shù)組next[n]的值)，那么n-next[n]就是要移動的長度（也是循環(huán)節(jié)所包含的字符個數(shù)，要是n%(n-next[n])=0就是所含的個數(shù)，/?否則就為1*/ 例如：a?? ?b?? ?a??? b?? ?a?? ?b next:-1?? 0??? 0??? 1??? 2??? 3??? 4 代碼懶得打了 #include<iostream> #include <stdio.h> #include<string.h> using namespace std; int next[1000005]; char s[1000005]; void getnext() {int i=0,j=-1;next[0]=-1;int len=strlen(s);while(i<len)//不同點{if(s[i]==s[j]||j==-1){i++;j++;next[i]=j;}elsej=next[j];} } int main() {while(scanf("%s",s)>0){if(s[0]=='.')break;int len=strlen(s);getnext();if(len%(len-next[len])==0)printf("%d\n",len/(len-next[len]));else//?printf("1\n");//?}return 0; } http://www.cnblogs.com/ziyi--caolu/archive/2013/01/01/2841708.html

總結(jié)

以上是生活随笔為你收集整理的POJ 2406 Power Strings (KMP) kmp循环节的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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