求最長回文子串——ManaCher算法

0.問題定義

最長回文子串：求任一既定字元串中，回文子串的最長長度

• 回文：正向和反向完全一樣的字元串叫做回文字元串
• 子串：從一個字元串中任意截取一段是這個字元串的子串

1. 暴力破解法

這是最容易想到的辦法。先周遊獲得字元串的所有子串，再對每個子串判斷其是不是回文串。

對于長度為n的字元串，子串個數為n(n-1)/2，加上對每個子串進行判斷，這種解法的時間複雜度為O(n^3)。代碼就不寫了，下面重點介紹Manacher算法

2. ManaCher算法

由回文的定義可以推出回文串有軸對稱的特性。是以可以從字元串的軸心點（可能是兩個字元中間的空位）開始向左右兩側同時進行比較，一直找到兩端不相同的字元為止，就是一個回文子串。

但這裡存在一個問題，字元串的長度可能為奇數，也可能為偶數。軸心點的位置可能是字元串中的某個字元，也可能是相鄰兩個字元之間的空位。對于從軸心點開始向兩側尋找邊界的方法來說，就需要對兩種情況都進行考慮。

2.1 解決回文子串長度奇偶性問題

難道需要每個字元位周遊兩次？ManaCher告訴你那個太複雜！ManaCher算法的第一個要點就是解決回文串長度奇偶性的問題。解決的方法很巧妙，在開始周遊之前先對母串進行預處理，在母串的首尾以及相鄰兩個字元之間插入一個母串中沒有出現的字元。這樣處理之後，所有的回文子串都會變為長度為奇數的回文串，也就是說，我們隻需要以每個字元為軸心來考慮即可。

其實我的個人了解就是，通過插入字元将原本是中間空位的軸心轉化為新字元串的一個字元

2.2 解決重複通路的問題

基于回文串的對稱性性質，我們可以發現，有很多回文子串其實是更長的一個回文子串的子串，而且這種子串會在更長的回文串的軸心兩側對稱出現。這種回文串顯然不是問題需要的答案，但不對其進行處理會浪費周遊的時間。ManaCher算法根據回文串的對稱性，對這種本質相同的回文串進行簡化處理。

首先，定義了三個變量：

• 定義一個

  回文半徑

  數組P。我們把一個回文串中最左或最右位置的字元與其對稱軸的距離稱為

  回文半徑

  。 用P[i]表示以第i個字元為對稱軸的回文串的回文半徑。
• 輔助變量

  max_right

  ，表示目前通路到的所有回文子串，所能觸及的最右一個字元的位置。
• 輔助變量

  center

  ，邊界最靠右的回文串的對稱軸所在的位置。有多個回文串最右邊在同一位置時，選擇軸心最靠左的記錄

新字元串的

回文半徑

就是原字元串的回文子串長度。那麼隻要我們求出了

P

數組，就能得到最長回文子串的長度。

我們從左往右地通路字元串來求

P

，假設目前通路到的位置為

i

，即要求

P[i]

1. 當

   i < max_right

   這就意味着位置為

   i

   的字元位于一個回文子串之中，這個回文子串的軸心是

   center

   ，回文半徑為

   max_right - center

   。根據回文的對稱性，可以得出一個公式：

   其中，

   P[2*center -i]<max_right-i

   的情況，

   p[i]

   是一定等于

   P[2*center -i]

   。但其他情況下并不能最終确定

   P[i]

   的值。怎麼辦？隻能是按照對稱性對比

   i

   兩側的字元，當然

   max_right - i

   這個半徑内的字元是不需要再進行比較的！

   如果

   i+P[i]>max_right

   則要更新

   max_right

   和

   center

   :
2. 當

   i>= max_right

   此時，位置為

   i

   的字元位于已知的回文子串外部或者邊界上，我們無法快速得知其回文半徑，隻能通過向兩側比較的方法。同樣需要對

   max_right

   和

   center

   進行更新，不再重複

對預處理過的字元串從左到右按照以上步驟進行周遊之後，我們就得到了所有位置的回文半徑數組

P

。求得其中最大值就是最長回文子串的長度了。

3. Python實作

由于最近在學習Python，是以用Python實作了一下ManaCher算法，代碼如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-

DEBUG = 1

#對字元串進行插值，插入#


def insert(target):

    result = "*"
    for i in range(len(target)):
        result += "#" + target[i]

    result += "#$"
    if DEBUG:
        print(result)
    return result


def manacher(target):
    target = insert(target)
    max_right = 0  # 回文子串的最右邊界
    center = 0  # 最右回文子串的軸心标記
    p = [0 for i in range(len(target))]  # 記錄每個軸心的回文子串半徑
    for i in range(2, len(target) - 2):
        if max_right > i:
            p[i] = min(p[2 * center - i], max_right - i)
        while target[i - p[i] - 1] == target[i + p[i] + 1]:
            p[i] += 1
        if i + p[i] > max_right:
            max_right = i + p[i]
            center = i
    if DEBUG:
        print("p=", p)
    return max(p)


if __name__ == '__main__':
    print(manacher('abc1234321ab'))
    print(manacher('asdflkjl'))
           

運作結果為：

*#a#b#c#1#2#3#4#3#2#1#a#b#$
('p=', [0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 7, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0])
7
*#a#s#d#f#l#k#j#l#$
('p=', [0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0])
1