介紹
Manacher於發現了一種線性時間算法，可以在列出給定字元串中從任意位置開始的所有回文子串。並且，Apostolico, Breslauer & Galil 發現，同樣的算法也可以在任意位置查找全部極大回文子串，並且時間複雜度是線性的。因此，他們提供了一種時間複雜度為線性的最長回文子串解法。另外，Jeuring (1994), Gusfield (1997)發現了基於後綴樹的算法。也存在已知的高效並行算法 。
最長回文子串算法不應當與最長回文子序列算法混淆。
例子
1. 問題描述
回文串（palindromic string）是指這個字元串無論從左讀還是從右讀，所讀的順序是一樣的；簡而言之，回文串是左右對稱的。所謂最長回文子串問題，是指對於一個給定的母串
2.窮舉法
最容易想到的是窮舉法，窮舉所有子串，找出是回文串的子串，統計出最長的那一個。
時間複雜度：判斷是否為回文串的複雜度為O(n)，longestPalindrome有雙層for循環，因此總的複雜度為為O(n3)。
空間複雜度：O(1)。
Manacher算法
遍歷
因為奇回文和偶回文在判斷時比較麻煩, 所以對str 進行處理,把每個字元開頭、結尾和中間插入一個特殊字元′#′來得到一個新的字元串數組。比如str=″bcbaa″,處理後為″#b#c#b#a#a#″,然後從每個字元左右擴出去的方式找最大回文子串就方便多了。對奇回文來說, 不這么處理也能通過擴的方式找到, 比如″bcb″,從′c′開始向左右兩側擴出去能找到最大回文。處理後為″#b#c#b#″,從′c′開始向左右兩側擴出去依然能找到最大回文。對偶回文來說, 不處理而直接通過擴的方式是找不到的,比如″aa″,因為沒有確定的軸,但是處理後為″#a#a#″,就可以通過從中間的′#′擴出去的方式找到最大回文。所以通過這樣的處理方式, 最大回文子串無論是偶回文還是奇回文, 都可以通過統一的“擴”過程找到,解決了差異性的問題。同時要說的是,這個特殊字元是什麼無所謂, 甚至可以是字元串中出現的字元, 也不會影響最終的結果, 就是一個純輔助的作用。
具體的處理過程請參看如下代碼中的manacherString 方法
最佳化
假設str 處理之後的字元串記為charArr。對每個字元(包括特殊字元)都進行“最佳化後”的擴過程。
擴過程
只要能夠從左到右依次算出數組pArr 每個位置的值,最大的那個值實際上就是處理後的charArr 中最大的回文半徑, 根據最大的回文半徑, 再對應回原字元串的話, 整個問題就解決了。步驟3就是從左到右依次計算出pArr 數組每個位置的值的過程 。
(1)假設計算到位置i 的字元charArr[i], 在i之前位置的計算過程中, 都會不斷地更新pR 和index的值,即位置i 之前的index 這個回文中心擴出了一個最右的回文邊界pR。
(2)如果pR-1 位置沒有包住當前的i 位置。比如“#c#a#b#a#c#”,計算到charArr[1]==’c’時,pR 為1。也就是說,右邊界在1 位置,1 位置為最右回文半徑即將到達但還沒有達到的位置, 所以當前的pR-1 位置沒有包住當前的i 位置。此時和普通做法一樣,從i 位置字元開始,向左右兩側擴出去檢查, 此時的“ 擴” 過程沒有獲得加速。
(3) 如果pR -1 位置包住當前的i 位置。比如“#c#a#b#a#c#”, 計算到charArr [6 … 10] 時,pR 都為11,此時pR-1 包住了位置6-10。這種情況下,檢查過程是可以獲得最佳化的,這也是manacher 算法的核心內容。
進階問題
按照步驟3 的邏輯從左到右計算出pArr 數組, 計算完成後再遍歷一遍pArr 數組, 找出最大的回文半徑,假設位置i 的回文半徑最大,即pArr[i]==max。但max 只是charArr 的最大回文半徑, 還得對應回原來的字元串, 求出最大回文半徑的長度( 其實就是max-1)。在charArr 中位置3 的回文半徑最大,最大值為4(即pArr[3]==4),對應原字元串的最大回文子串長度為4-1=3。
Manacher 算法時間複雜度是O(N)的證明。雖然我們可以很明顯地看到Manacher 算法與普通方法相比,在擴出去檢查這一行為上有明顯的最佳化, 但如何證明該算法的時間複雜度就是O(N)呢？ 關鍵之處在於估算擴出去檢查這一行為發生的數量。原字元串在處理後的長度由N 變為2N,從步驟3 的主要邏輯來看,要么在計算一個位置的回文半徑時完全不需要擴出去檢查,比如,步驟3 的中3)介紹的情況一和情況二,都可以直接獲得位置i 的回文半徑長度； 要么每一次擴出去檢查都會讓回文半逕到達更右的位置,當然會使pR更新。然而pR 最多是從-1 增加到2N(右邊界),並且從來不減小, 所以擴出去檢查的次數就是O (N) 的級別。所以Manacher 算法時間複雜度是O(N)。具體請參看如下代碼中的maxLcpsLength 方法。
在字元串的最後添加最少字元, 使整個字元串都成為回文串, 其實就是查找在必須包含最後一個字元的情況下, 最長的回文串是什麼。那么之前不是最長回文子串的部分逆序過來, 就是應該添加的部分。比如“abcd123321”,在必須包含最後一個字元的情況下,最長的回文子串是“123321”,之前不是最長回文子串的部分是“abcd”, 所以末尾應該添加的部分就是“dcba”。那么只要把manacher 算法稍作修改就可以。具體改為： 從左到右計算回文半徑時, 關注回文半徑最右即將到達的位置(pR),一旦發現已經到達最後(pR== charArr.length),說明必須包含最後一個字元的最長回文半徑已經找到, 直接退出檢查過程, 返回該添加的字元串即可。具體過程參看如下代碼中的shortestEnd
方法。
