1725 . Massacre at Camp Happy
TopCoder
Tags
Description
你有聽過Massacre at Camp Happy這個遊戲嗎？
有一個很快樂的營隊，叫做快樂營。快樂營的參與者都十分快樂，他們絲毫不知道接下來會變成一盤盤人肉沙西米。
因為外星生物食肉蚯登陸地球了！
食肉蚯非常喜歡吃肉，舉凡小松鼠、烏龜、黃鼠狼、小山豬都吃得很開心。
但是他很怕吃到同伴，畢竟食肉蚯在地球上十分稀少。
我們假定地球上每一種生物長相都可以用一個小寫字母字串表示。
而對兩種生物甲和乙"k-完全相同"的定義是把生物乙前k個字母"搬移"最尾端，然後兩個字串會長得一模一樣。
例如aaab和baaa就是"1-完全相同"。
可是任兩隻食肉蚯是不可能"完全相同"的。他們頂多是"幾乎相同"。
"k-幾乎相同"意即把生物乙前k個字母"搬移"最尾端時，會和生物甲恰好一個字元不一樣。
現在食肉蚯看到了一隻獵物，他知道如果獵物和他"幾乎相同"的話就表示不能吃，因為獵物應該也是食肉蚯。
當然幾乎相同也可能不只一種。
例如aaa和aab就是0-幾乎相同、1-幾乎相同、2-幾乎相同。食肉蚯想要求出所有的k使得他跟獵物"k-幾乎相同"。
如果是"完全相同"或是不同，那就吃了獵物吧。
Input Format
輸入第一行有一個正整數N，表示生物長相字串的長度(1<=N<=1,000,000)。
接下來有兩行，各包含N個字元小寫英文字母字串，表示食肉蚯的長相和獵物的長相。
Output Format
如果該生物跟食肉蚯幾乎相同，
第一行輸出一個字串"TAK"(不含雙引號，在食肉蚯語中表示"同類")、
第二行由小到大輸出許多個以空白分隔、[0, N-1]內的整數，表示所有可能的k。
反之僅輸出一行包含一個字串"NIE"(不含雙引號，在食肉蚯語中表示"吃了他!")
Sample Input 1
ababa
aaaab
Sample Output 1
2 4
Sample Input 2
ababa
bbbbb
Sample Output 2
Sample Input 3
aaaab
caaaa
Sample Output 3
4
Hints
Problem Source
原TIOJ1725 / Adapted From PA 2007 Round 6 Prawie równoważne słowa
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 3 |
| 2 | 1 | 3 |
| 3 | 2 | 3 |
| 4 | 3 | 3 |
| 5 | 4 | 3 |
| 6 | 5 | 3 |
| 7 | 6 | 3 |
| 8 | 7 | 3 |
| 9 | 8 | 3 |
| 10 | 9 | 3 |
| 11 | 10 | 3 |
| 12 | 11 | 3 |
| 13 | 12 | 3 |
| 14 | 13 | 3 |
| 15 | 14 | 3 |
| 16 | 15 | 3 |
| 17 | 16 | 3 |
| 18 | 17 | 3 |
| 19 | 18 | 3 |
| 20 | 19 | 3 |
| 21 | 20 | 3 |
| 22 | 21 | 3 |
| 23 | 22 | 3 |
| 24 | 23 | 3 |
| 25 | 24 | 3 |
| 26 | 25 | 3 |
| 27 | 26 | 3 |
| 28 | 27 | 3 |
| 29 | 28 | 3 |
| 30 | 29 | 3 |
| 31 | 30 | 3 |
| 32 | 31 | 3 |
| 33 | 32 | 4 |