abaabcac

0 1 1 2 2 3 1 2

#include<iostream>

#include<string>

#include<cstring>

using namespace std;

int next[10005];

char str[10005];

int len;

void getnext(char *str,int next[])

{

    int j,k;

	next[1]=0;

	j=1;

	k=0;

	while(j<=len)

		if((k==0)||(str[j]==str[k]))

		{

			++j;

			++k;

			next[j]=k;

		}

		else

			k=next[k];

}

int main()

{

	char s[1005];

	cin>>s;

	len =strlen(s);

	int j,k;

	for(j=1,k=0;k<len;j++,k++)

	{

		str[j]=s[k];

	}

	int i;

	getnext(str,next);

	for(i=1;i<len;i++)

        cout<<next[i]<<" ";

	cout<<next[len]<<endl;

	return 0;

}