回分類題庫
h158: F.非對稱之美
關鍵字: NPSC 2015 高中組決賽

測資點 : 8 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 38 Times / 34 Users | Submit : 84 Times / 40 Users | Accepted rate : 85%
題目加入時間 : 2016-09-09 10:26

Content: 简体中文

對稱的事物往往令人感到美麗。

回文就是一個對稱的例子。當一個字串反過來寫依然不變的時候我們就說它是一個回文。例如「上海自來水來自海上」和 "noon" 都是回文;而 "XDD" 則不是回文。在一個字串中找出最長的回文子字串也是資訊競賽中的經典題型,藉由精巧的 Manacher's algorithm 可以在線性時間內解決這個問題。

但太多對稱的東西也讓人感到審美疲勞,競賽中只考察經典題也有點無聊。字串界之王蚯蚯決定要另闢蹊徑,探索非對稱之美。因此他想要考考你,如何在字串 s 中,找出最長的「非回文」子字串呢?

蚯蚯很好心的提醒你有關子字串的定義。如果一個字串 t 與 s 中的一個連續區段相等的話,我們就說 t 是 s 的一個子字串。例如 s = "meow" 時,"meow" 跟 "eo" 都是 s 的子字串;而 "mw" 則不是。 

Input:

輸入的第一行有一個整數 T,代表共有幾筆測試資料。 

每筆測試資料恰有一行,包含一個字串 s。

Output:

對於每筆測試資料請輸出一個正整數於一行,代表 s 的最長非回文子字串的長度。如果 s 中的所有子字串都是回文的話,請輸出 0。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
meow
aaaa
noon

Sample Output :

4
0
3

Hint :

Author :

NPSC 2015 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum