1905(kmp).cpp

zoj的1905题. KMP算法的标准程序。

//zoj 1905 KMP
/*
设串长为len,先求出next[len]
然后判断len是否能被len - next[len] 整除,能则输出len / (len - next[len])
不能输出1
*/

#include <iostream.h>
#include <string>

using namespace std;

int next[1000002];
string str;

void get_next(string T,int next[])
{
 int i=1,j=0;
 next[1]=0;
 while(i<=T.length())
 {
    if(j==0 || T[i]==T[j])
    { ++i;++j;
      if(T[i]!=T[j]) next[i]=j;
      else next[i]=next[j];//消去多余的可能的比较,next再向前跳
    }
    else j=next[j];

 }
}

int main()
{
  int len;
  
  while(cin>>str && str!=".")
  {
    len=str.length();
    get_next(str,next);
    if(len%(len-next[len])==0)
    cout<<len/(len-next[len])<<endl;
    else
    cout<<"1"<<endl;
  }
}