TopCoder

Thumb tumblr m6532itd121rnos1s
$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

94.1% (16/17)

Submission's AC Ratio

23.3% (34/146)

Description

球主有個怪癖。

定義S的k-位移(k<S的長度)是把S的前k個字移到S的最後端。
(所以abcde的2-位移就是cdeab,所有字串的0-位移是自己)

球主很喜歡告訴別人一個字串S,然後問別人S的所有k-位移中,有多少個是回文?
看到別人無法在1.5秒之內答出來,他總是感到非常的得意
由於他的日子過得很空虛,他就靠著這樣一個愚蠢的行為來建立他的存在感

但有一天他做了一個噩夢
他夢見自己在夢中自己問了自己這樣一個問題,題目是一個長為174629的字串,他卻花了3.7秒才答出來
球主簡直難過得快哭了。

請你寫個程式來幫幫球主吧!
為了他的存在感以及你的AC題數。
當然,你的程式必須夠有效率,否則若無法滿足球主自己定出來的標準,他可是會感到自卑的!

Input Format

輸入只有一行,為一字串S

S的長度<=1000000

Output Format

若沒有任何S的k-位移是回文, 請輸出"none" (不含雙引號)

否則請輸出num: k1 k2 k3 ... knum
代表共有num個k使得S的k-位移是回文,而這些k值分別是k1,k2...knum (由小到大輸出)

行末請勿輸出空格。

Sample Input

abba

Sample Output

2: 0 2

Hints

0-位移為abba
2-位移為baab
皆為回文

Problem Source

原TIOJ1321 / TIOJ IOI Warmup III, 2008. Problemsetter: kelvin

Subtasks

For Testdata: 0 ~ 0, Score: 5
For Testdata: 1 ~ 1, Score: 5
For Testdata: 2 ~ 2, Score: 5
For Testdata: 3 ~ 3, Score: 5
For Testdata: 4 ~ 4, Score: 5
For Testdata: 5 ~ 5, Score: 5
For Testdata: 6 ~ 6, Score: 5
For Testdata: 7 ~ 7, Score: 5
For Testdata: 8 ~ 8, Score: 5
For Testdata: 9 ~ 9, Score: 5
For Testdata: 10 ~ 10, Score: 5
For Testdata: 11 ~ 11, Score: 5
For Testdata: 12 ~ 12, Score: 5
For Testdata: 13 ~ 13, Score: 5
For Testdata: 14 ~ 14, Score: 5
For Testdata: 15 ~ 15, Score: 5
For Testdata: 16 ~ 16, Score: 5
For Testdata: 17 ~ 17, Score: 5
For Testdata: 18 ~ 18, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 3500 65536
1 3500 65536
2 3500 65536
3 3500 65536
4 3500 65536
5 3500 65536
6 3500 65536
7 3500 65536
8 3500 65536
9 3500 65536
10 3500 65536
11 3500 65536
12 3500 65536
13 3500 65536
14 3500 65536
15 3500 65536
16 3500 65536
17 3500 65536
18 3500 65536