題目
思路
- 求最小循環(huán)節(jié)
- 完全循環(huán)就是周期溜腐，不能完全循環(huán)就是1
AC代碼
#include<iostream>
using namespace std;
const int MAXN=10000002;
string P;
string T;
int NEXT[MAXN];
int plen,tlen;
void getNEXT(){
NEXT[0] = -1;
int k = -1 ;
int j = 0 ;
while(j<plen){
if(k==-1||P[k]==P[j]){
NEXT[++j] = ++k;
}else{
k = NEXT[k];
}
}
}
int main(){
ios::sync_with_stdio(false);
while(cin>>P&&"."!=P){
plen=P.length();
getNEXT();
int length = plen - NEXT[plen];
int ans;
if(plen%length == 0){
ans = plen/length;
}else ans = 1;
cout<<ans<<"\n";
}
return 0;
}
