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