基本介紹
- 中文名：最長回文子串問題
- 領域：計算機
介紹,例子,Manacher算法,遍歷,最佳化,擴過程,進階問題,
介紹
Manacher於發現了一種線性時間算法，可以在列出給定字元串中從任意位置開始的所有回文子串。並且，Apostolico, Breslauer & Galil 發現，同樣的算法也可以在任意位置查找全部極大回文子串，並且時間複雜度是線性的。因此，他們提供了一種時間複雜度為線性的最長回文子串解法。另外，Jeuring (1994), Gusfield (1997)發現了基於後綴樹的算法。也存在已知的高效並行算法。
最長回文子串算法不應當與最長回文子序列算法混淆。
例子
1. 問題描述
回文串（palindromic string）是指這個字元串無論從左讀還是從右讀，所讀的順序是一樣的；簡而言之，回文串是左右對稱的。所謂最長回文子串問題，是指對於一個給定的母串
abcdedcb
2.窮舉法
最容易想到的是窮舉法，窮舉所有子串，找出是回文串的子串，統計出最長的那一個。
// check whether a string is palindromicfunc isPalindromic(s string) bool { mid := len(s) / 2 last := len(s) - 1 for i := 0; i < mid; i++ { if s[i] != s[last - i] { return false } }return true} // longest palindromic substringfunc longestPalindrome(s string) string { last := len(s) - 1 longest := string(s[0]) for i := 0; i < last; i++ { for j := i + 1; j <= last; j++ { if isPalindromic(s[i:j + 1]) && j + 1 - i > len(longest) { longest = s[i:j+1] } } } return longest}時間複雜度：判斷是否為回文串的複雜度為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 方法
public char[] manacherString(String str) {char[] charArr=str.toCharArray();char[] res=new char[str.length()*2+1];int index=0;for (i=0;I ! =res.length;i++){res[i]=(i&1)==0?’#’:charArr[index++];}Return res;}最佳化
假設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 方法。
public static int maxLcpsLength(String str){ if (str == null || str.length() == 0) { return 0;}char[] charArr = manacherString(str);int[] pArr = new int[charArr.length];int index = -1;int pR = -1;int max = Integer.MIN_VALUE;for (int i = 0; i ! = charArr.length; i++) { pArr [i] = pR > i ? Math.min (pArr [2 * index - i], pR - i) : 1; while (i + pArr[i] < charArr.length && i- pArr[i] > -1) { if (charArr [i + pArr [i]] == charArr[i - pArr[i]]) pArr[i]++; else { break; } } if (i+pArr[i] >pR) { pR = i + pArr[i]; index = i; } max = Math.max(max, pArr[i]); } return max -1;}在字元串的最後添加最少字元, 使整個字元串都成為回文串, 其實就是查找在必須包含最後一個字元的情況下, 最長的回文串是什麼。那么之前不是最長回文子串的部分逆序過來, 就是應該添加的部分。比如“abcd123321”,在必須包含最後一個字元的情況下,最長的回文子串是“123321”,之前不是最長回文子串的部分是“abcd”, 所以末尾應該添加的部分就是“dcba”。那么只要把manacher 算法稍作修改就可以。具體改為： 從左到右計算回文半徑時, 關注回文半徑最右即將到達的位置(pR),一旦發現已經到達最後(pR== charArr.length),說明必須包含最後一個字元的最長回文半徑已經找到, 直接退出檢查過程, 返回該添加的字元串即可。具體過程參看如下代碼中的shortestEnd
方法。
方法。
public static String shortestEnd(String str) { if (str == null || str.length() == 0) { return null; }char[] charArr = manacherString(str); int[] pArr = new int[charArr.length]; int index=-1; int pR=-1; int maxContainsEnd = -1; for (int i = 0; i ! = charArr.length; i++) { pArr [i] = pR > i ? Math.min (pArr [2 *index - i], pR - i) : 1; while (i + pArr[i] < charArr.length && i- pArr[i] > -1) { if (charArr [i + pArr [i]] == charArr[i - pArr[i]]) pArr[i]++; else { break; } }if (i + pArr[i] > pR) {pR = i + pArr[i]; index = i; }if (pR == charArr.length) { maxContainsEnd = pArr[i]; break; } } char [] res = new char [str.length () -maxContainsEnd + 1]; for (int i = 0; i < res.length; i++) { res[res.length - 1 - i] = charArr [i * 2+ 1]; } return String.valueOf(res);}