644 . 回文好玩好文回

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

1xlc

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

80.0% (4/5)

Tags

apcsc apcsc-timecomplexity

Description

東周年間，孔子的得意門生顏淵有一個很特別的技能：如果有人給他一個字串 $S$，他就可以以極快的速度找到這個字串的最長回文子字串！在一個「字串」、「回文」、「子字串」這些名詞都還沒被定義的年代，這是一件極為了不起的事情。比較不為人知的事，這也是顏淵又名「顏回」的原因。

一些名詞定義：如果一個字串被反過來之後，它還是長得一樣，則他就稱為一個回文。舉例來說，cabac、唧唧復唧唧 都是回文，但是 abcde、木蘭當戶織 則都不是。如果一個字串 $A$ 能夠刪除頭尾若干連續的字元而得到 $B$，則稱 $B$ 為$A$ 的子字串。

論語中記載著：

哀公問：「弟子孰為好學？」孔子對曰：「有顏回者好學，不遷怒，不貳過。不幸短命死矣！今也則亡，未聞好學者也。」

在顏回去世後的兩千年，科技已經有了極大的進步，可以重新複製顏回那時候的技能了！請你寫一支程式來找到一個字串 $S$ 的最長回文子字串吧！

Input Format

輸出只有一行，就是需要在其中搜尋的字串 $S(1 \leq |S| \leq 5000)$，且保證 $S$ 只由小寫英文字母組成。

Output Format

第一行請輸出一個數字 $L$，代表 $S$ 當中的最長子字串的長度。第二行請輸出兩個數字 $l,r(1 \leq l \leq r \leq |S|$，且 $r - l + 1 = L)$，代表 $S_lS_{l + 1}\dots S_{r}$ 為 $S$ 的最長回文子字串。如果有多組答案，則輸出任何一者皆可。詳細的格式請參照範例。

Sample Input 1

ntucsieies

Sample Output 1

3
6 8

Sample Input 2

apcscamp

Sample Output 2

3
3 5

Sample Input 3

loremipsumdolorsitamet

Sample Output 3

3
12 14

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~21 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 1 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
Submit
Back to Top