POJ - 2406

/*H E A D*/
int nxt[maxn];
char P[maxn];
void buildNext(){
    nxt[1]=0;
    int j=0,m=strlen(P+1);
    rep(i,2,m){
        while(j&&P[i]!=P[j+1])j=nxt[j];
        if(P[i]==P[j+1])j++;
        nxt[i]=j;
    } 
}
int main(){
    while(~s1(P)){
        int m=strlen(P+1);
        if(P[1]==‘.‘&&m==1)break;
        buildNext();
        if(m%(m-nxt[m])==0) printf("%d\n",m/(m-nxt[m]));
        else printf("1\n");//note
    }
    return 0;
}