POJ 2752 Seek the Name, Seek the Fame(KMP求公共前后缀)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#define maxn 1000005
using namespace std;
char s[maxn];
int pre[maxn], Next[maxn];
int cnt;

void init(){
  int j = 0, k = -1;
  memset(Next, -1, sizeof(Next));
  int len = strlen(s);
  while(j < len){
    if(k == -1 || s[j] == s[k]){
      k ++;
      j ++;
      Next[j] = k;
    }
    else k = Next[k];
  }
}

int main()
{
  while(~scanf("%s", s)){
    init();
    int len = strlen(s);
    cnt = 0;
    int xx = Next[len];
    while(xx){
      pre[cnt ++] = xx;
      xx = Next[xx];
    }
    for(int i=cnt-1;i>=0;i--){
      printf("%d ", pre[i]);
    }
    printf("%d\n", len);
  }
  return 0;
}