POJ 2752

//KMP,对vector单个赋值不懂，只能用c语言形式拉 
//大致题意：字符串s有多少个子串既是前缀又是后缀 
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
using namespace std;
const int N = 400010;
int next[N] = {0},a[N] = {0};
void get_next(string s)
 {
     int i,j;
     i=0;
     j=-1;
     next[0]=-1;
     while(i<s.length())
     {
         if(j==-1||s[i]==s[j])
         {
             ++i;
             ++j;
             next[i]=j;
         }
         else
             j=next[j];
     }
 }
int main()
{
    int i,j,k,T;
    string s;
    while(cin>>s)
    {
        get_next(s);
        k = s.length();
        j =0;
        while(k>0)
        {
            a[j++] = next[k];
            k = next[k];
        }
        for(i=j-2;i>=0;i--)//a[j-1]等于0 
            cout<<a[i]<<" ";                       
        cout<<s.length()<<endl;
        memset(a,0,sizeof(a));
        memset(next,0,sizeof(next));
        s.clear();
    }
  //  system("pause");
    return 0;
}