终于靠着理解写出KMP了,两种KMP要代码中这种才能求循环节。i-next[i]就是循环节。
#include<cstdio>
#define N 1000005
char s[N];
int next[N];
void solve(){
int ans;
int k=-1,i=0;
next[i]=k;
while(s[i]){
if(k==-1||s[i]==s[k]){//记住两个都是等于
i++;
k++;
next[i]=k;
}else
k=next[k];
}
ans=i-next[i];
if(i%ans)ans=1;
else ans=i/ans;
printf("%d\n",ans);
}
int main(){
while(~scanf("%s",s)&&s[0]!='.')
solve();
}