题目描述
明湖大仙在算命上十分出名,因此很多夫妻都翻山越岭的找他给自己刚出生的孩子起名字。在起了无数个名字以后,大仙感到这个工作十分无聊,于是想到了一个简单但有效的算法来给新生儿取名:
第一步,将父母的名字连接在一起得到新的字符串S。
第二步,找到一个子串使得该子串既是S的前缀也是S的后缀。
举个例子,爸爸的名字叫"ala",妈妈的名字是"la",那么S="ala"+"la"="alala",于是新生儿可以取的名字分别是"a","ala","alala"。现在大仙希望你可以帮忙编写一个程序来计算每个新生儿所有可以取的名字的长度。
输入描述
输入包含多行,为题目所述的字符串S。
提示:输入只有小写字母,且S的长度不超过400000。
输出描述
对于输入的每个S,递增输出一行整数,表示新生儿姓名可能的长度,两个整数间以空格隔开。
样例输入
alala
babcba
样例输出
1 3 5
2 6
提示