【POJ 2406】Power Strings（KMP循环节）

终于靠着理解写出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
",ans);
}
int main(){
    while(~scanf("%s",s)&&s[0]!='.')
        solve();
}