2024 全國模擬賽題目上線啦 !!!!! 題目在這裡～
1321 . 好多回文 ndromePali
TopCoder
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 |