一本通 1466 Power Strings

找字符串的最短循环节

#include <bits/stdc++.h>
using namespace std ; 
const int N=1e6+1;
 char a[N];
 int n,p[N];
 
 void init(){
      int i,j=0;
      
      for(i=1;i<n;i++){
            while(j>0&&a[i+1]!=a[j+1]) j=p[j];
            if(a[i+1]==a[j+1]) j++;
            
            p[i+1]=j;
     }
 }
 int main(){
     while(cin>>a+1,a[1]!='.'){
         n=strlen(a+1);
         init();
         if(n%(n-p[n])) cout<<1<<endl;
         else  cout<<n/(n-p[n])<<endl;
    }
 }