POJ 1961 C++ （KMP）

#include

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("%dn",&n),n!=0)

　　　　 { for(i=1;i<=n;i++)

　　　　　　　　s[i]=getchar();

　　　　　 s[i]='#';

　　　　　 Get_next();

　　　　　 printf("Test case #%dn",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 %dn",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