POJ 1961 C++ （KMP）

#include<iostream>
using namespace std;
int n,next[1000008];
char s[1000008];
void Get_next()
{int j,k;
j=1;
k=0;
next[1]=0;
while(j<=n+1)
　　　 { if(k==0 || s[j]==s[k])
　　　　　　{ j++;
　　　　　　　k++;
　　　　　　　next[j]=k;
　　　　　　 }
　　　　　else
　　　　　　 k=next[k];
　　　　 }
}
int main()
{ int i,cnt,k;
　 freopen("in.txt","r",stdin);
　 freopen("out.txt","w",stdout);
　 k=1;
　while(scanf("%d\n",&n),n!=0)
　　　　 { for(i=1;i<=n;i++)
　　　　　　　　s[i]=getchar();
　　　　　 s[i]='#';
　　　　　 Get_next();
　　　　　 printf("Test case #%d\n",k++);
　　　　　 for(i=2;i<=n;i++)
　　　　　　　　if(i%(i+1-next[i+1])==0)
　　　　　　　　　　{ cnt=i/(i+1-next[i+1]);
　　　　　　　　　　　if(cnt!=1)
　　　　　　　　　　　printf("%d %d\n",i,cnt);
　　　　　　　　　　 }
　　　　printf("\n");
　　 }
　 return 0;
}

該題的題意是這樣的，給若干個字符串，判斷該字符串的前n位最多重復了幾次，比如， 給ababab，結果是前4位重復了2次，前6位重復了3次，忽略重復一次的情況.現在我們將注意 力放在一個給定的字符串重復了多少次，然後做一個循環就可以求出所有的結果。

我們要根據kmp算法中的next函數來解決這個問題，以ababab為例加以說明：

String：ababab

Next： 0112345

這裡根據後面的需要多計算了一位next值。

我們用ababab即作為主串有作為模式串來進行匹配，假設匹配到第7為時不匹配了(下標中 1開始)，要根據next[7](=5)的值繼續匹配：

ababab*

ababab&

ababab*

ababab

這樣，我們用（length+1）-next[length+1]就是字符串向右移動的位數，在該例中為7- 5=2.然後用總的長度除以這個向右移動的位數，如果能除盡的話，結果就是重復的次數，否 則重復的次數為1