poj 2752 Seek the Name, Seek the Fame（kmp）

传送门

题目大意

求一个字符串的所有前缀

题解

求i的nxt,nxt的nxt...

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[500009];
int k,n,len,nxt[500009],ans[500009];
void getnext(){
    for(int i=2,j=0;i<=len;i++){
        while(s[i]!=s[j+1]&&j)j=nxt[j];
        if(s[i]==s[j+1])nxt[i]=++j;
    }
}
int main(){
    while(scanf("%s",s+1)!=EOF){
        n=0;memset(nxt,0,sizeof(nxt));
        len=strlen(s+1);
        getnext();k=len;
        while(len){
            ans[++n]=nxt[len];
            len=nxt[len];
        }
        for(int i=n-1;i;i--)printf("%d ",ans[i]);
        printf("%d
",k);
    }
    return 0;
}