Time Limits: 1000 ms Memory Limits: 65536 KB

Description

俗话说“好命不如好名”，小h准备给他的宠物狗起个新的名字，于是他把一些英文的名字全抄下来了，写成一行长长的字符串，小h觉得一个名字如果是好名字，那么这个名字在这个串中既是前缀，又是后缀，即是这个名字从前面开始可以匹配，从后面开始也可以匹配，例如abc在 abcddabc中既是前缀，也是后缀，而ab就不是，可是长达4*10^5的字符让小h几乎昏过去了，为了给自己的小狗起个好名字，小h向你求救，并且他要求要将所有的好名字的长度都输出来。

Input

一行，要处理的字符串（都是小写字母）。

Output

一行若干个数字，从小到大输出，表示好名字的长度。

Sample Input

1
abcddabc

Sample Output

1
3 8

Data Constraint

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
const int max=4e5+1;
char s[max];
int next[max] = {-1},ans[max],len,j=0,k=-1;
int main(){
	scanf("%s", s);
	while(s[j]!='\0'){
		if(k==-1||s[j]==s[k])
			next[++j]=++k;
		else{
			 k=next[k];
		}
	}
	while(j){
		ans[++len]=j;
		j=next[j];
	}
	for(int i=len;i;i--)
		printf("%d ",ans[i]);
	return 0;
}