Manacher 算法講解

一：背景

給定一個字符串，求出其最長迴文子串。例如：

1. s="abcd"，最長迴文長度爲 1；
2. s="ababa"，最長迴文長度爲 5；
3. s="abccb"，最長迴文長度爲 4，即bccb。

以上問題的傳統思路大概是，遍歷每一個字符，以該字符爲中心向兩邊查找。其時間複雜度爲$O(n^2)$，效率很差。

1975年，一個叫Manacher的人發明了一個算法，Manacher算法（中文名：馬拉車算法），該算法可以把時間複雜度提升到$O(n)$。下面來看看馬拉車算法是如何工作的。

二：算法過程分析

由於迴文分爲偶迴文（比如 bccb）和奇迴文（比如 bcacb），而在處理奇偶問題上會比較繁瑣，所以這裏我們使用一個技巧，具體做法是：在字符串首尾，及各字符間各插入一個字符（前提這個字符未出現在串裏）。

舉個例子：s="abbahopxpo"，轉換爲s_new="$#a#b#b#a#h#o#p#x#p#o#"（這裏的字符 $ 只是爲了防止越界，下面代碼會有說明），如此，s 裏起初有一個偶迴文abba和一個奇迴文opxpo，被轉換爲#a#b#b#a#和#o#p#x#p#o#，長度都轉換成了奇數。

定義一個輔助數組int p[]，其中p[i]表示以 i 爲中心的最長迴文的半徑，例如：

可以看出，p[i] - 1正好是原字符串中最長迴文串的長度。

接下來的重點就是求解 p 數組，如下圖：

設置兩個變量，mx 和 id 。mx 代表以 id 爲中心的最長迴文的右邊界，也就是mx = id + p[id]。

假設我們現在求p[i]，也就是以 i 爲中心的最長迴文半徑，如果i < mx，如上圖，那麼：

if (i < mx)  
    p[i] = min(p[2 * id - i], mx - i);

2 * id - i爲 i 關於 id 的對稱點，即上圖的 j 點，而p[j]表示以 j 爲中心的最長迴文半徑，因此我們可以利用p[j]來加快查找。

三：代碼

#include <iostream>  
#include <cstring>
#include <algorithm>  

using namespace std;

char s[1000];
char s_new[2000];
int p[2000];

int Init()
{
    int len = strlen(s);
    s_new[0] = '$';
    s_new[1] = '#';
    int j = 2;

    for (int i = 0; i < len; i++)
    {
        s_new[j++] = s[i];
        s_new[j++] = '#';
    }

    s_new[j] = '\0';  // 別忘了哦
    
    return j;  // 返回 s_new 的長度
}

int Manacher()
{
    int len = Init();  // 取得新字符串長度並完成向 s_new 的轉換
    int max_len = -1;  // 最長迴文長度

    int id;
    int mx = 0;

    for (int i = 1; i < len; i++)
    {
        if (i < mx)
            p[i] = min(p[2 * id - i], mx - i);  // 需搞清楚上面那張圖含義, mx 和 2*id-i 的含義
        else
            p[i] = 1;

        while (s_new[i - p[i]] == s_new[i + p[i]])  // 不需邊界判斷，因爲左有'$',右有'\0'
            p[i]++;

        // 我們每走一步 i，都要和 mx 比較，我們希望 mx 儘可能的遠，這樣才能更有機會執行 if (i < mx)這句代碼，從而提高效率
        if (mx < i + p[i])
        {
            id = i;
            mx = i + p[i];
        }

        max_len = max(max_len, p[i] - 1);
    }

    return max_len;
}

int main()
{
    while (printf("請輸入字符串：\n"))
    {
        scanf("%s", s);
        printf("最長迴文長度爲 %d\n\n", Manacher());
    }
    return 0;
}

四：算法複雜度分析

文章開頭已經提及，Manacher算法爲線性算法，即使最差情況下其時間複雜度亦爲$O(n)$，在進行證明之前，我們還需要更加深入地理解上述算法過程。

根據迴文的性質，p[i]的值基於以下三種情況得出：

（1）：j 的迴文串有一部分在 id 的之外，如下圖：

上圖中，黑線爲 id 的迴文，i 與 j 關於 id 對稱，紅線爲 j 的迴文。那麼根據代碼此時p[i] = mx - i，即紫線。那麼p[i]還可以更大麼？答案是不可能！見下圖：

假設右側新增的紫色部分是p[i]可以增加的部分，那麼根據迴文的性質，a 等於 d ，也就是說 id 的迴文不僅僅是黑線，而是黑線+兩條紫線，矛盾，所以假設不成立，故p[i] = mx - i，不可以再增加一分。

（2）：j 迴文串全部在 id 的內部，如下圖：

根據代碼，此時p[i] = p[j]，那麼p[i]還可以更大麼？答案亦是不可能！見下圖：

假設右側新增的紅色部分是p[i]可以增加的部分，那麼根據迴文的性質，a 等於 b ，也就是說 j 的迴文應該再加上 a 和 b ，矛盾，所以假設不成立，故p[i] = p[j]，也不可以再增加一分。

（3）：j 迴文串左端正好與 id 的迴文串左端重合，見下圖：

根據代碼，此時p[i] = p[j]或p[i] = mx - i，並且p[i]還可以繼續增加，所以需要

while (s_new[i - p[i]] == s_new[i + p[i]]) 
    p[i]++;

根據（1）（2）（3），很容易推出Manacher算法的最壞情況，即爲字符串內全是相同字符的時候。在這裏我們重點研究Manacher（）中的for語句，推算髮現for語句內平均訪問每個字符5次，即時間複雜度爲：$T_{worst}(n)=O(n)$。

同理，我們也很容易知道最佳情況下的時間複雜度，即字符串內字符各不相同的時候。推算得平均訪問每個字符4次，即時間複雜度爲：$T_{best}(n)=O(n)$。

綜上，Manacher算法的時間複雜度爲$O(n)$。