POJ 2406

#if 0
#include <stdio.h>
#define XSIZE 1000001
char str[XSIZE];
int  next[XSIZE],len;
int kmpNext(char*x,int*next){
    int i,j;
    for(i=0,j=next[0]=-1;x[i];){
        for(;j>-1&&x[i]!=x[j];j=next[j]);
        ++i;++j;
        next[i]=x[i]==x[j]?next[j]:j;
    }
    return i;
}
int main() {
    for(;scanf("%str",str),*str!='.';printf("%d\n",len%(next[0]=len-next[len])?1:len/next[0]))
        len=kmpNext(str,next);
    return 0;
}
#else
char s[1000001];n[1000001],i,j;main(){for(;gets(s),*s-'.';printf("%d\n",i%(j=i-n[i])?1:i/j))for(i=0,j=*n=-1;s[i];++i,++j,n[i]=s[i]==s[j]?n[j]:j)for(;j>-1&&s[i]!=s[j];j=n[j]);}
#endif