题解：UVA10298 Power Strings

求解每个字符串的最短循环子串

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000005;
int p[maxn];
char a[maxn];
int n;
void init(){
    int j=0;
    p[1]=0;
    for(int i=2; i<=n; i++){
        while(j && a[j+1]!=a[i]) j=p[j];
        if(a[i]==a[j+1]) j++;
        p[i]=j;
    }
}
int main(){
    for(;;){
        scanf("%s",a+1);
        if(a[1]=='.') break;
        n=strlen(a+1);
        init();
        if(n%(n-p[n])==0) printf("%d
",n/(n-p[n]));
        else printf("1
");
    }
    return 0;
}