poj 1961 Period

链接:poj 1961

题意：给你一个字符串，求这个字符串首字符到第i个字符为止的子串的最大循环次数k(k>1),若存在，输出i和k.

比如aabaabaabaab，长度为12.

到第2个字符时，a出现2次,到第6个字符时，aab出现了2次，

到第9个字符时，aab出现3次，到第12个字符时，aab出现4次

分析：这个就是求给定字符串的前缀子串（包括整个串）的最大循环次数，根据next数组即可

如果一个字符串长度为n:

if(n%(n-next[n])==0)

最小循环长度为  L=n-next[n];

最大循环次数为  S=n/L=n/(n-next[n]);

#include<stdio.h>
#include<string.h>
int next[1001010]={-1};
char s[1001010];
void getnext(int n)
{
    int i=0,j=-1;
    while(i<n){
        if(j==-1||s[i]==s[j]){
            i++;
            j++;
            next[i]=j;
        }
        else
            j=next[j];
    }
}
int main()
{
    int n,i,j,k=0,m;
    while(scanf("%d",&n)!=EOF){
        if(n==0)
            break;
        scanf("%s",s);
        k++;
        printf("Test case #%d\n",k);
        getnext(n);
        for(i=1;i<n;i++){
            j=i+1;
            if(j%(j-next[j])==0){
                m=j/(j-next[j]);
                if(m>1)
                    printf("%d %d\n",j,m);
            }
        }
        printf("\n");
    }
    return 0;
}