学步园

next数组的应用。。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int const MAXN = 1000010;
char s[MAXN];
int next[MAXN];
void Get_N(int l){
    memset(next,0,sizeof(next));
    for(int i = 1;i < l;i++){
        int j = next[i];
        while(j && s[i] != s[j]) j =  next[j];
        if(s[j] == s[i]) next[i + 1] = j + 1;
        else next[i + 1] = 0;
    }
   /* for(int i = 1;i <= l;i++){
        cout<<next[i]<<" ";
    }
    cout<<endl;*/
}
int main(){
    while(cin>>s){
        if(s[0] == '.') break;
        int l = strlen(s);
        Get_N(l);
        if(next[l] && l % (l - next[l]) == 0) printf("%d\n",l / (l - next[l]));
        else printf("1\n");
    }
    return 0;
}