最長回文子串問題

最長回文子串一般指本詞條

在計算機科學中,最長回文子串或最長對稱因子問題是在一個字元串中查找一個最長的連續的回文的子串,例如“banana”最長回文子串是“anana”。最長回文子串並不一定是唯一的,比如“abracadabra”,沒有超過3的回文子串,但是有兩個回文字串長度都是3:“ada”和“aca”。在一些套用中,我們求出全部的極大回文子串(不被其他回文串包含的回文子串)。

基本介紹

  • 中文名:最長回文子串問題
  • 領域:計算機
介紹,例子,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);}

相關詞條

熱門詞條

聯絡我們