最長回文子串——Manacher 算法

mingzhong 發布于2019-07-24 18:10 / 1746人閱讀

摘要：問題定義最長回文子串問題給定一個字符串，求它的最長回文子串長度?？梢圆捎脛討B規劃，列舉回文串的起點或者終點來解最長回文串問題，無需討論串長度的奇偶性。

0. 問題定義

最長回文子串問題：給定一個字符串，求它的最長回文子串長度。

如果一個字符串正著讀和反著讀是一樣的，那它就是回文串。下面是一些回文串的實例：

12321    a    aba    abba    aaaa   tattarrattat（牛津英語詞典中最長的回文單詞）

1. Brute-force 解法

對于最長回文子串問題，最簡單粗暴的辦法是：找到字符串的所有子串，遍歷每一個子串以驗證它們是否為回文串。一個子串由子串的起點和終點確定，因此對于一個長度為n的字符串，共有n^2個子串。這些子串的平均長度大約是n/2，因此這個解法的時間復雜度是O(n^3)。

2. 改進的方法

顯然所有的回文串都是對稱的。長度為奇數回文串以最中間字符的位置為對稱軸左右對稱，而長度為偶數的回文串的對稱軸在中間兩個字符之間的空隙?？煞窭眠@種對稱性來提高算法效率呢？答案是肯定的。我們知道整個字符串中的所有字符，以及字符間的空隙，都可能是某個回文子串的對稱軸位置?？梢员闅v這些位置，在每個位置上同時向左和向右擴展，直到左右兩邊的字符不同，或者達到邊界。對于一個長度為n的字符串，這樣的位置一共有n+n-1=2n-1個，在每個位置上平均大約要進行n/4次字符比較，于是此算法的時間復雜度是O(n^2)。

3. Manacher 算法

對于一個比較長的字符串，O(n^2)的時間復雜度是難以接受的。Can we do better?

先來看看解法2存在的缺陷。

1) 由于回文串長度的奇偶性造成了不同性質的對稱軸位置，解法2要對兩種情況分別處理；
2) 很多子串被重復多次訪問，造成較差的時間效率。

缺陷2）可以通過這個直觀的小?體現：

char: a b a b a
  i : 0 1 2 3 4

當i==1，和i==2時，左邊的子串aba分別被遍歷了一次。

如果我們能改善解法2的不足，就很有希望能提高算法的效率。Manacher正是針對這些問題改進算法。

(1) 解決長度奇偶性帶來的對稱軸位置問題

Manacher算法首先對字符串做一個預處理，在所有的空隙位置(包括首尾)插入同樣的符號，要求這個符號是不會在原串中出現的。這樣會使得所有的串都是奇數長度的。以插入#號為例：

aba  ———>  #a#b#a#
abba ———>  #a#b#b#a#

插入的是同樣的符號，且符號不存在于原串，因此子串的回文性不受影響，原來是回文的串，插完之后還是回文的，原來不是回文的，依然不會是回文。

(2) 解決重復訪問的問題

我們把一個回文串中最左或最右位置的字符與其對稱軸的距離稱為回文半徑。Manacher定義了一個回文半徑數組RL，用RL[i]表示以第i個字符為對稱軸的回文串的回文半徑。我們一般對字符串從左往右處理，因此這里定義RL[i]為第i個字符為對稱軸的回文串的最右一個字符與字符i的距離。對于上面插入分隔符之后的兩個串，可以得到RL數組：

char:    # a # b # a #
 RL :    1 2 1 4 1 2 1
RL-1:    0 1 0 3 0 1 0
  i :    0 1 2 3 4 5 6

char:    # a # b # b # a #
 RL :    1 2 1 2 5 2 1 2 1
RL-1:    0 1 0 1 4 1 0 1 0
  i :    0 1 2 3 4 5 6 7 8

上面我們還求了一下RL[i]-1。通過觀察可以發現，RL[i]-1的值，正是在原本那個沒有插入過分隔符的串中，以位置i為對稱軸的最長回文串的長度。那么只要我們求出了RL數組，就能得到最長回文子串的長度。

于是問題變成了，怎樣高效地求的RL數組。基本思路是利用回文串的對稱性，擴展回文串。

我們再引入一個輔助變量MaxRight，表示當前訪問到的所有回文子串，所能觸及的最右一個字符的位置。另外還要記錄下MaxRight對應的回文串的對稱軸所在的位置，記為pos，它們的位置關系如下。

我們從左往右地訪問字符串來求RL，假設當前訪問到的位置為i，即要求RL[i]，在對應上圖，i必然是在po右邊的(obviously)。但我們更關注的是，i是在MaxRight的左邊還是右邊。我們分情況來討論。

1）當i在MaxRight的左邊

情況1)可以用下圖來刻畫：

我們知道，圖中兩個紅色塊之間（包括紅色塊）的串是回文的；并且以i為對稱軸的回文串，是與紅色塊間的回文串有所重疊的。我們找到i關于pos的對稱位置j，這個j對應的RL[j]我們是已經算過的。根據回文串的對稱性，以i為對稱軸的回文串和以j為對稱軸的回文串，有一部分是相同的。這里又有兩種細分的情況。

以j為對稱軸的回文串比較短，短到像下圖這樣。

這時我們知道RL[i]至少不會小于RL[j]，并且已經知道了部分的以i為中心的回文串，于是可以令RL[i]=RL[j]。但是以i為對稱軸的回文串可能實際上更長，因此我們試著以i為對稱軸，繼續往左右兩邊擴展，直到左右兩邊字符不同，或者到達邊界。

以j為對稱軸的回文串很長，這么長：

這時，我們只能確定，兩條藍線之間的部分（即不超過MaxRight的部分）是回文的，于是從這個長度開始，嘗試以i為中心向左右兩邊擴展，，直到左右兩邊字符不同，或者到達邊界。

不論以上哪種情況，之后都要嘗試更新MaxRight和pos，因為有可能得到更大的MaxRight。

具體操作如下：

step 1: 令RL[i]=min(RL[2*pos-i], MaxRight-i)
step 2: 以i為中心擴展回文串，直到左右兩邊字符不同，或者到達邊界。
step 3: 更新MaxRight和pos

2）當i在MaxRight的右邊

遇到這種情況，說明以i為對稱軸的回文串還沒有任何一個部分被訪問過，于是只能從i的左右兩邊開始嘗試擴展了，當左右兩邊字符不同，或者到達字符串邊界時停止。然后更新MaxRight和pos。

(3) 算法實現

#Python
def manacher(s):
    #預處理
    s="#"+"#".join(s)+"#"

    RL=[0]*len(s)
    MaxRight=0
    pos=0
    MaxLen=0
    for i in range(len(s)):
        if i=0 and i+RL[i]MaxRight:
            MaxRight=RL[i]+i-1
            pos=i
        #更新最長回文串的長度
        MaxLen=max(MaxLen, RL[i])
    return MaxLen-1

(4) 復雜度分析

空間復雜度：插入分隔符形成新串，占用了線性的空間大??；RL數組也占用線性大小的空間，因此空間復雜度是線性的。
時間復雜度：盡管代碼里面有兩層循環，通過amortized analysis我們可以得出，Manacher的時間復雜度是線性的。由于內層的循環只對尚未匹配的部分進行，因此對于每一個字符而言，只會進行一次，因此時間復雜度是O(n)。

4. 更多關于回文串的 fun facts（參考自維基百科）

4.1 人們在一座名為赫庫蘭尼姆的古城遺跡中，找到了一個好玩的拉丁語回文串：sator arepo tenet opera rotas。翻譯成中文大概就是`一個叫做Arepo的播種者，他用力地扶（把）著車輪。這個串的每個單詞首字母剛好組成了第一個單詞，每個單詞的第二個字母剛好組成了第二個單詞...于是乎，如果寫出醬紫，你會發現上下左右四個方向讀起來是一樣的。這個串被稱為 Sator Square.

4.2 本文開頭給出的單詞tattarrattat，出現在愛爾蘭作家詹姆斯·喬伊斯的小說《尤利西斯》，是敲門的意思。吉尼斯紀錄的最長回文英文單詞是detartrated，是個化學術語。另外，還有些已出版的英文回文小說（你們歪果仁真會玩），比如Satire: Veritas，Dr Awkward & Olson in Oslo等。

2015.11.9 更新。

可以采用動態規劃，列舉回文串的起點或者終點來解最長回文串問題，無需討論串長度的奇偶性。
看下面的扎瓦代碼，容易理解。

    public int longestPalindrome(String s) {
     int n=s.length();
     boolean[][] pal=new boolean[n][n];
     //pal[i][j] 表示s[i...j]是否是回文串
     int maxLen=0;
     for (int i=0;i=0){
             if (s.charAt(j)==s.charAt(i)&&(i-j<2||pal[j+1][i-1])){
                 pal[j][i]=true;
                maxLen=Math.max(maxLen, i-j+1);
             }
             j--;
         }
     }
     return maxLen;
    }

GPU云服務器云服務器最長公共子串 java最長相同子串最大公共子串算法最大連續子串算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/37625.html

LeetCode——Longest Palindromic Substring

摘要：題目即求最長回文子序列原題鏈接此篇博客僅為學習記錄我的解法及代碼暴力解決，用及進行兩層遍歷循環中套一層循環，用遍歷，求最長回文序列字符串，同時用變量記錄最長子序列這種寫法很暴力，效率很低，一層循環，一層循環，回文序列對比一層，時間復雜度為辣題目： Given a string s, find the longest palindromic substring in s. You ma...

shevy 2019-08-23 18:26 評論0 收藏0
Manacher算法

摘要：若他的子串為回文串，則相對于對稱的另一端子串必然是回文串?；匚拇囟ㄊ侵行膶ΨQ的，也就是。目前確定的是回文半徑范圍內能確定的值，對于半徑外的字符因為不知能能否和已知回文串繼續構成更大回文串，所以也要進行判斷。今天思考一道題的時候，學習了一些思路，其中 Manacher 算法很有必要記錄下來。本文參考了：http://blog.csdn.net/ggggiqny... 這道題的內容是：...

buildupchao 2019-08-21 11:36 評論0 收藏0
最長回文子串

摘要：給定一個字符串，找到中最長的回文子串。你可以假設的最大長度為。示例輸入輸出注意也是一個有效答案。給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。示例 1：輸入: babad輸出: bab注意: aba 也是一個有效答案。示例 2：輸入: cbbd輸出: bb 用的Manacher算法 var longestPalindrome = fu...

jemygraw 2019-08-23 14:44 評論0 收藏0
獲取最長回文子串

摘要：以下是最長回文子串的相關代碼，相關邏輯已在注釋中注明我們原有的字符串可能存在兩種回文子串，一種是具有基數個元素例如一種是具有偶數個元素例如這樣的話分情況判斷比較復雜所以我們對原字符串進行擴充在相鄰元素中插入特殊值插入后的原基數回文子串變成了以下是最長回文子串的Manacher‘s Algorithm相關代碼，相關邏輯已在注釋中注明： public static String solu...

ymyang 2019-08-19 11:46 評論0 收藏0
[Leetcode] Longest Palindromic Substring 最長回文子字符串

摘要：這種解法中，外層循環遍歷的是子字符串的中心點，內層循環則是從中心擴散，一旦不是回文就不再計算其他以此為中心的較大的字符串。 Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length ...

KnewOne 2019-08-14 12:17 評論0 收藏0