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) Output Limit (KiB)
0 3500 65536 262144
1 3500 65536 262144
2 3500 65536 262144
3 3500 65536 262144
4 3500 65536 262144
5 3500 65536 262144
6 3500 65536 262144
7 3500 65536 262144
8 3500 65536 262144
9 3500 65536 262144
10 3500 65536 262144
11 3500 65536 262144
12 3500 65536 262144
13 3500 65536 262144
14 3500 65536 262144
15 3500 65536 262144
16 3500 65536 262144
17 3500 65536 262144
18 3500 65536 262144