[IOI Camp Judge]串珠吊飾 (題目備份)

IOI Camp Judge是暫時性的，因此在這裡作個題目備份，請大家參考～

題解在這裡

串珠吊飾

Time Limit: 5s

Description

蘿蘿和莉莉一起串了一個環狀的珠珠項鍊，她們想要把項鍊切成兩段等長的珠珠串當作手機吊飾。

對一個珠串 S，定義 S 的前綴為 {S}∪(S拿掉最後一個珠子的前綴)，例如：abcd 的前綴集合 ={a,ab,abc,abcd}。

定義兩個珠串 S0,S1 的最長共同前綴為 S0 前綴和 S1 前綴的交集中最長的那一個，例如：aab 和 aaa 的最長共同前綴為 aa。

切開來的珠串可以從右邊或從左邊當作吊飾的頭端，友情度為兩串吊飾從頭端到尾端的最長共同前綴。

給你一個珠珠項鍊 S，請你告訴蘿蘿和莉莉切出來的吊飾友情度最大可以多大。

換句話說，給你一個珠串 S，請你幫助她們計算 max{f(CA,B):ABC=S,|A|+|C|=|B|}

其中 LCP(X,Y) 為字串 X 與 Y 的最長共同前綴，f(X,Y)=max(LCP(X,Y),LCP(X,YR),LCP(XR,Y),LCP(XR,YR))

上標 R 代表把珠串整個翻轉，例如 aabbcR=cbbaa。

Input Format

第一行有一個正整數 T，代表總共有幾筆測試資料。每筆測試資料的第一行有一個由小寫字母組成的字串，代表珠珠項鍊，每種字母代表一種珠珠。

• 1≤T≤20
• 2≤ 珠串長度 ≤105
• 珠串長度為偶數

Output Format

對於每筆測試資料，輸出一行一個數字表示珠珠項鍊切出來吊飾友情度的最大值。

Sample Input

4
aaaaab
ab
bbaaaa
bzzaczza

Sample Output

2
0
3
3

Hint

• 第一筆測試資料可以切成 aaa 與 aab，兩者的最長共同前綴為 aa。
• 第二筆測試資料只能切成 a 與 b，兩者的最長共同前綴長度為 0。
• 第三筆測試資料可以切成 baa 與 aab，我們將 baa 反轉後可得到最長共同前綴 aab。
• 第四筆測試資料可以切成 zzac 與 zzab，兩者的最長共同前綴為 zza。