POJ - 2752 Seek the Name, Seek the Fame（KMP）

POJ - 2752 Seek the Name, Seek the Fame

找当前串的最大相同前缀后缀，找到一个后，令该相同前缀后缀为当前串，再循环调用，直到循环到P[0]=-1的位置

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N = 400010;
char b[N];
int ne[N],m;
void get_next()
{
    for(int i=2,j=0;i<=m;i++){
    while(j&&b[i]!=b[j+1]) j=ne[j];if(b[i]==b[j+1]) j++;ne[i]=j;}
}
int main()
{
    while(scanf("%s",b+1)!=EOF){
    m=strlen(b+1);get_next();vector<int> a;int j=ne[m];while(j) a.push_back(j),j=ne[j];for(int i=a.size()-1;i>=0;i--)printf("%d ",a[i]);printf("%d\n",m);}return 0;
}