Description：

Solution：

Code：

#include<bits/stdc++.h>

using namespace std;

int n;

#define MAXN 100010

char c[MAXN];

struct node

{

	int tr[26];

	int len,fail;

}s[MAXN];

int ptr,last;

int newnode(int l){s[ptr].len = l;return ptr++;}

void init()

{

	ptr = last = 0;

	memset(s,0,sizeof(s));

	newnode(0);newnode(-1);

	s[0].fail = 1;

	return;

}

int getfail(int i,int p)

{

	while(c[i - s[p].len - 1] != c[i])p = s[p].fail;

	return p;

}

void extend(int i,int k)

{

	int p = getfail(i,last);

	if(s[p].tr[k] == 0)

	{

		int np = newnode(s[p].len + 2);

		s[np].fail = s[getfail(i,s[p].fail)].tr[k];

		s[p].tr[k] = np;

	}

	last = s[p].tr[k];

	return;

}

int main()

{

	scanf("%s",c + 1);

	n = strlen(c + 1);

	init();

	for(int i = 1;i <= n;++i)

	{

		extend(i,c[i] - 'a');

		printf("%d",ptr - 2);

		if(i == n)puts("");

		else putchar(' ');

	}

	return 0;

}