Problem2868--漂亮的毛毛雨

2868: 漂亮的毛毛雨

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 43  Solved: 35
[Submit] [Status] [Web Board] [Creator:]

Description

很久以前,有着一位毛毛雨学姐,人美脾气大,但是因为毛毛雨学姐实在太漂亮了,所以那时候的大家都对她百依百顺的。而zser,很明显,他也喜欢毛毛雨学姐。众所周知,毛毛雨学姐最讨厌的就是复读机,所以她给了zser一个任务。把每天群里的复读机全部记下来。很快,群里面的复读机就都不敢进行最低级的复读了。复读机们用了一种全新的方式复读。就是说那种可能自己就重复的话。比如:haha,就可以看成是重复了"ha"。所以现在zser又有了新工作,就是记录下每一句话中,在某个位置,如果当前的子串可以看是新形式的"复读",就打印这个位置和"复读"的最大的次数。

Input

输入T。(T<=20)
每组里面有一个字符串str。长度小于5e5。

Output

按照题目描述输出。

Sample Input Copy

3
hahaha
dddd
mmy

Sample Output Copy

4 2
6 3
2 2
3 3
4 4
2 2

HINT

"hahaha",在下标为3的时候,"haha"可以看成是由两个"ha"复读得到。所以输出4 2。当下标为5时,"hahaha"可以看成是由三个"ha"复读得到。所以输出6 3。
"ddd",在下标为3时,"dddd"可以看成是"dd"复读得到,也可以看成是"d"复读得到。最大次数为4。
输出4 4。

Source/Category

KMP