TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

81.8% (45/55)

Submission's AC Ratio

23.5% (101/430)

Tags

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 1

abba

Sample Output 1

2: 0 2

Hints

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

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 5
2 1 5
3 2 5
4 3 5
5 4 5
6 5 5
7 6 5
8 7 5
9 8 5
10 9 5
11 10 5
12 11 5
13 12 5
14 13 5
15 14 5
16 15 5
17 16 5
18 17 5
19 18 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3500 65536 262144 1
1 3500 65536 262144 2
2 3500 65536 262144 3
3 3500 65536 262144 4
4 3500 65536 262144 5
5 3500 65536 262144 6
6 3500 65536 262144 7
7 3500 65536 262144 8
8 3500 65536 262144 9
9 3500 65536 262144 10
10 3500 65536 262144 11
11 3500 65536 262144 12
12 3500 65536 262144 13
13 3500 65536 262144 14
14 3500 65536 262144 15
15 3500 65536 262144 16
16 3500 65536 262144 17
17 3500 65536 262144 18
18 3500 65536 262144 19