最長回文（Manacher）

​​HOT~ 杭電2015級新生如何加入ACM集訓隊？

​​

最長回文

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 12244    Accepted Submission(s): 4501

Problem Description

給出一個隻由小寫英文字元a,b,c...y,z組成的字元串S,求S中最長回文串的長度.

回文就是正反讀都是一樣的字元串,如aba, abba等

Input

輸入有多組case,不超過120組,每組輸入為一行小寫英文字元a,b,c...y,z組成的字元串S

兩組case之間由空行隔開(該空行不用處理)

字元串長度len <= 110000

Output

每一行一個整數x,對應一組case,表示該組case的字元串中所包含的最長回文長度.

Sample Input

aaaaabab

Sample Output

43

 題解：manacher算法：可以求出字元串每個位置的最長字串；

if( mx > i)

    p[i]=MIN( p[2*id-i],

mx-i);

就是目前面比較的最遠長度mx>i的時候，P［i］有一個最小值。這個算法的核心思想就在這裡，為什麼P數組滿足這樣一個性質呢?

   （下面的部分為圖檔形式）

代碼：