題目連結：
題目大意：
給定一正整數 T ，代表有 T 筆測試資料。每筆測試資料一列，每列給定一個字串 S （此字串長度不會超過 500,000 個字元）。求在 S 之中最長的迴文字串之長度為何？
範例輸入：
4
radar
hollow
cat
enhance
範例輸出：
5
4
1
1
解題思維：
（2021 / 4 / 15 重新編排、修飾文句並新增一些圖例）
本題有一個只需 O(n) 時間複雜度便可求得最長迴文子字串長度之演算法，其名為
Manacher's Algorithm
其精神源自於從字串中每個字元當作中心往兩側延伸所得的最長迴文。而本演算法是重複利用先前的字元計算過的迴文而推得當前字元作為中心的最長迴文。演算法內容如下：
定義一函數 Z(i)，其代表以 S 的第 i 個字元為中心（也就是以此字元為中心往左右擴張）的最長迴文長度的一半。所以 S 的第 i - Z(i) ～ 第 i + Z(i) 個字元即是一個迴文。如下圖：
但是因為是以一個字元為中心，所以迴文長度必定是奇數的，偶數長度的迴文將無法被包含到。
因此，可以在原字串的每個字元間加（頭尾也要）上都加上一個沒有在裡面出現的字元。例如： S ＝ "ABC" ，則經過以上步驟後可能變為 "-A-B-C-" 。因此原先奇數、偶數長度之迴文現在長度統一為奇數。
而 Z(i) 的求法可以利用已經求得的 Z(j) 們（j ＜ i）。因此當有迴文位於另一迴文內或是重疊的時候，便可以省下一些不必要的計算。方法如下：
一開始，我們先判斷最靠近 i （也就是越右側的）的 j + Z(j) 是否大於 i （即判斷先前的迴文有沒有任何一個有覆蓋到 S[i] 這個字元）。同時，我們將迴文 j - Z(j) ～ j + Z(j) 的左界 j - Z(j) 定為 L 、右界 j + Z(j) 定為 R。
一：如果 R < i ，則先前求出的所有 Z(j) 通通派不上用場。因此直接從第 i 個字元慢慢擴張，判斷新擴張到的兩個字元是否相等，以此求解（如下圖）。
二：如果 R ≧ i ，代表著 S[i] 存在於 L ～ R 這個迴文裡，且 S[i] 位於迴文後半部。所以 S[i] 也會出現在 L ～ S[j] （也就是前半部）這段字串之中。假設 i 以 j 為中心鏡射過去後的位置為 i'（也就是 S[i] 在前半部的位置） ，如下圖：
則會有以下三種情況：
其之一：i + Z(i') < R，也就是 i + Z(i') 會被 R 給框住。因為從 Z(i') 可知 S[i' - Z(i') - 1] （下面定為 A）≠ S[i' + Z(i') + 1] （下面定為 B）且已知 L ～ Ｒ 為一迴文。
因此 S[i' - Z(i') - 1] = A 且 S[i + Z(i') + 1] = B，因而 S[i - Z(i') - 1] ≠ S[i + Z(i') + 1]。因此 Z(i) ＝ Z(i')。如下圖所示。
其之二：i + Z(i') = R ，代表 i + Z(i') 剛好落在邊界 R 。因為此時不能像上面一樣確認 S[i - Z(i') - 1] 和 S[i + Z(i') + 1] 的關係（S[i + Z(i') + 1] 不在迴文 L ～ R 中）。因此需要從 S[i + Z(i')] 開始向右擴張並判斷，才可知道正確的 Z(i) 。如下圖。
其之三：i + Z(i') > R，從 Z(i') 可得，S[j - Z(j) - 1] 與以 i' 作為中心鏡射過去的位置為相同字元（因為 Z(i) 之緣故。設該位置為 P）。
再加上 P 必定位於 L ～ R 之內，所以 P 有一鏡射位置（鏡射中心為 j） P' ，兩者為同一字元。
此時 P' 到 i 的距離 = i 到 j + Z(j) + 1 之距離。已知 S[j - Z(j) - 1] 和 S[j + Z(j) + 1] 不是同一個字元（根據 Z(j) 之定義）。所以 P' 跟 S[j + Z(j) + 1] 一定不是同一字元。因此 S[i] 往右到 j + Z(j) 後無法繼續向右擴張。所以 Z(i) = j + Z(j) - i 。見下圖。
求出所有 Z(i) 之後，其中最大的 Z(i) 值即是最大的迴文字串長度（根據實作方法不同，視情況而定需要將該值減去 1）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
