Power Strings POJ - 2406（kmp最小循环节）

AC代码：

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e6+5;
string s;
int nxt[maxn];
void getnext(){
  int i=0,k=-1;
  nxt[0]=-1;
  while(i<s.size()){
    if(k==-1||s[i]==s[k])nxt[++i]=++k;
    else k=nxt[k];
  }
}
int main(){
  while(cin>>s){
    if(s[0]=='.')break;
    memset(nxt,0,sizeof(nxt));
    int len=s.size();
    getnext();
    if(len%(len-nxt[len])==0)cout<<len/(len-nxt[len])<<endl;
    else cout<<1<<endl;
  }
}