POJ 2752 Seek the Name, Seek the Fame(KMP)

题意

给出一个字符串问有多少长度，使这个长度的前缀等于这个长度的后缀。

n<=400000

题解

考虑nxt数组的意义。我们发现构建nxt数组时，一直跳nxt数组就是在枚举，所有前缀和后最相等的长度。

所以我们求出nxt数组，然后一直跳nxt[len]就好了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=500000;
char s[N];
int nxt[N],ans[N];
void dfs(int x){
    if(nxt[x]<=0)return;
    dfs(nxt[x]);
    printf("%d ",nxt[x]);
}
int main(){
    while(scanf("%s",s+1)!=EOF){
        int len=strlen(s+1);
            nxt[1]=0;
            for(int i=2,j=0;i<=len;i++){
            while(j&&s[j+1]!=s[i])j=nxt[j];
            if(s[j+1]==s[i])j++;
            nxt[i]=j;
        }
        dfs(len);
        printf("%d
",len);
    }
    return 0;
}