最長回文子串

最長回文子串（英語：Longest palindromic substring）是電腦科學中的問題，在一個字串中尋找一個最長的連續的回文的子串，例如「banana」最長回文子串是「anana」。最長回文子串並不一定是唯一的，比如在「abracadabra」中，沒有超過3個字元的回文子串，但是有兩個回文字串長度都是3：「ada」和「aca」。在一些應用中，我們求出全部的極大回文子串（不被其他回文串包含的回文子串）。

Glenn Manacher 於1975年發現了一種線性時間演算法^[1]，可以在列出給定字串中從任意位置開始的所有回文子串。並且，Apostolico, Breslauer & Galil ^[2]發現，同樣的演算法也可以在任意位置尋找全部極大回文子串，並且時間複雜度是線性的。因此，他們提供了一種時間複雜度為線性的最長回文子串解法。另外，Jeuring (1994)^[3], Gusfield (1997)^[4]發現了基於字尾樹的演算法。也存在已知的高效並列演算法。

最長回文子串演算法不應當與最長回文子序列演算法混淆。

定義

回文字串

如果一個長度為 $n$ 的字串 $s$ 當中所有字元依次為 $s_{0},\,s_{1},\,s_{2}\,\cdots \,s_{n-1}$ . 且 $s$ 滿足 $\forall i\in \left[0,\left\lfloor {\frac {n}{2}}\right\rfloor \right],\;s_{i}=s_{n-i-1}$ , 那麼則稱 $s$ 為一個回文字串。

最長回文子串

如果字串 $s$ 的一個回文子串 $s_{1}$ 是 $s$ 所有回文子串中長度最長的，那麼則稱 $s_{1}$ 為 $s$ 的最長回文子串。

暴力迴圈

在了解Manacher演算法之前，我們先了解一下「笨」辦法，也就是暴力迴圈，或者說死算。

注意到每個回文字串都是以一個對稱點為中心左右對稱的，所以暴力運算的方式是我們迴圈每個字母作對稱點，然後在每個對稱點檢視所能找到的最大回文字串的長度，最終得到結果。

偶長度回文字串的處理

需要注意到的一點，就是如果單純的把每個字元當作對稱點的話，只能得到奇數長度的回文字串符。而回文字串可能是偶數長度的，比如「cbaabd」中的「baab」，此時對稱點是介於兩個字元「a」中間的。這樣的話，如果直接處理起來，可能會比較麻煩，比如需要額外定義如何表示字元中間的位置。

這裏有一種巧妙的辦法，就是在字串中插入一些定位符，比如「$」，比如字串「cbaabd」就會變成「$c$b$a$a$b$d$」。

此時我們只需要按照奇長度字串的處理方式去處理這個字串（即每次選取對稱點只需依次選取字元），最後得到的回文字串「$b$a$a$b$」中，再把定位符「$」去掉，我們就可以得到原始的偶長度字串「baab」了。

偽代碼

将输入字符串s插入定位符，比如"$"
定义一个数组P[i]，用于存储以i位置为对称中心的最长回文字符串的“半径”
for c = 0 to len(s) do

    // 找到最长回文字符串“半径”
    r = 0
    while c-(r+1) >= 0 and c+(r+1) < len(s) and s[c+(r+1)] == s[c-(r+1)] do
        r = r + 1
    end while
    p[c] = r
end for
找到P[i]中的最大值P[x]
取出返回字符串 ret = substring(s, x-P[x], x+P[x])
将ret字符串中的定位符去除
return ret

時間複雜度

因為我們巢狀迴圈2次，外迴圈是n次，內迴圈平均下來是n/2次，所以時間複雜度是 $O(n^{2})$ 。

馬拉車演算法

馬拉車演算法（英語：Manacher's algorithm）利用回文字串和子回文字串中觀察到的一些特點，以在線性時間內找出字串的最長回文子串。

首先我們觀察一下回文字串可知，回文字串都是對稱的。而且如果一個長回文字串的對稱點左面包含一個小的回文字串，那麼對稱過去到右面也必然會包含一個小的回文字串，比如「dacabacad」這個字串中，對稱點b左面有一個回文字串「aca」，右面也會對稱出一個回文字串「aca」。

回文字串邊界的情況討論

那麼我們觀察對稱點左面出現的這個小回文字串，這個字串有三種情況：

情況1

如果左側小回文字串的左邊界在大回文字串的左邊界之內，那麼右面對稱出的小回文字串也不會觸碰到大回文字串的右邊界。

比如「dacaxacad」這個字串，左側的「aca」沒有超過這個大回文字串的左邊界，那麼右面對稱出的「aca」也不會超過右邊界。

也就是說，在這種情況下，右面這個小回文字串的長度與對稱的小回文字串的長度相等，絕對不會超過這個大回文字串。

情況2

如果左側小回文字串的左邊界超過了大回文字串的左邊界，那這個右面對稱出的小回文字串會正好觸碰到大回文字串的右邊界，但是不會超出。

比如觀察這個字串「dcbabcdxdcbabce」。左側的小回文字串的邊界超出了用底線標出的大回文字串的左邊界。對稱過來的右側的小回文字串的邊界會剛好卡在大回文字串的右邊界。這是由於大回文字串右邊界之外的下一個字母（此處是「e」）絕對不是左邊界的那個字母「d」的對稱，所以右邊的小回文字串延申到邊界之後也無法繼續延申下去了。

也就是說，在這種情況下，右面這個小回文字串的右邊界與大回文字串的右邊界相同，那麼這個小回文字串的長度也絕對不會超過這個大回文字串。

情況3

如果左側小回文字串的左邊界正好卡在大回文字串的左邊界上，那麼右面對稱出的小回文字串有可能會繼續延伸下去，超過大回文字串的右邊界。

比如觀察這個字串「abcdcbabcdxdcbabcdxdcb"，左邊的小回文字串的左邊界正好卡在大回文字串的左邊界上，那麼對稱過來的大回文字串是有可能繼續延申下去的。比如在這個例子中，右面以「a」為對稱點的小回文字串一直能向右延申到整個字串的結尾。

也就是說，在這種情況下，右面這個小回文字串的右邊界至少與大回文字串的右邊界相同，並且有可能會延申。也就是說這個小回文字串的長度可能會超過這個大回文字串。

總結

我們考慮了左邊的小回文字串的邊界與大回文字串邊界的三種情況，只有情況3，也就是正好邊界在同一位置的時候，右側的小回文字串的長度才有可能會超過大回文字串，而其他兩種情況的話，我們可以跳過不去計算。

所以Manacher演算法在先找到一個長回文字串之後，可以選擇性的跳過很多字母，無需一一計算，與暴力迴圈相比極大了提升了演算法的效率。

偽代碼

將輸入字元串s插入定位符，比如"$"
定義一個數組P[i]，用於存儲以i位置為對稱中心的最長迴文字元串的“半徑”

// 第一個字母就是以第一個字母為中心的最長迴文字元串
r = 0  
c = 0
P[0] = 0

while c < len(s) do
    // 找到最長迴文字元串“半徑”
    while c-(r+1) >= 0 and c+(r+1) < len(s) and s[c+(r+1)] == s[c-(r+1)] do
        r = r + 1
    end while
    p[c] = r

    // 存儲最大迴文字元串
    lc = c
    lr = r
    // 計算右邊界
    rb = lc + lr
    
    // 循環到右邊界，看看有哪些能跳過
    c = c + 1
    r = 0
    while c <= rb do
        // 找到對稱的位置mc
        mc = lc - (c - lc)      
        if c + P[mc] < rb then
            // 情況1，可跳過
            P[c] = P[mc]    // 能跳過的話，不賦值也可以
        else if c + P[mc] > rb then
            // 情況2，可跳過
            P[c] = rb - c   // 能跳過的話，不賦值也可以
        else
            // 情況3，無法跳過，需要計算
            // 不過我們知道“半徑”至少能到達右邊界
            r = rb - c
            break
        end if
        
        c = c + 1
    end while
end while
找到P[i]中的最大值P[x]
取出返回字元串 ret = substring(s, x-P[x], x+P[x])
將ret字元串中的定位符去除
return ret

時間複雜度

假設我們每次迴圈能找到的大回文字串的長度為m，然後我們可以一直跳過計算，直接從該字串的右邊界開始繼續迴圈。如果字串的總長度為n，那麼我們只需n/m次這樣的迴圈即可。而確定ｍ的長度需要內迴圈ｍ次。這樣來說，總時間複雜度是(n/m)*m，也就是 $O(n)$ 。

實現

Python

注意，以下代碼並未完全按照Manacher演算法執行，並未分情況討論，即無論是情況1/2/3中的哪種情況都嘗試向外繼續探測半徑能否延申。

雖然這樣會多幾次無用的嘗試，但是代碼會簡單一些。

另外需要注意的是，這段代碼並非返回最長回文字串。

def manacher(s0 : str) -> list:
    T = '$#' + '#'.join(s0) + '#@'
    l = len(T)
    P = [0] * l
    R, C = 0, 0
    for i in range(1,l-1):
        if i < R:
            P[i] = min(P[2 * C - i], R - i)
        
        while T[i+(P[i]+1)] == T[i-(P[i]+1)]:
            P[i] += 1
        
        if P[i] + i > R:
            R = P[i] + i
            C = i
    return P

C++

constexpr auto MAXN = (int)7000000;

char s[MAXN << 1], str[MAXN];
int RL[MAXN];

int Manacher(void) {
	size_t len = strlen(str); *s = '#';
	for (int i = 0; i < len; i++) {
		s[(i << 1) + 1] = str[i]; s[(i << 1) + 2] = '#';
	}len = (len << 1) + 1;

	int max = 1, pos, maxRight = -1; memset(RL, 0, sizeof(RL));
	for (int i = 0; i < len; i++) {
		if (i < maxRight) RL[i] = std::min(RL[(pos << 1) - i], maxRight - i);
		else RL[i] = 1;
		while (i - RL[i] >= 0 && i + RL[i] < len && s[i - RL[i]] == s[i + RL[i]])++RL[i];
		if (i + RL[i] > maxRight) { pos = i; maxRight = i + RL[i]; }
		max = std::max(max, RL[i] - 1);
	} return max;
}

Matlab

function m = Manacher(a)
    T = ['$#' reshape([a;ones(size(a))*'#'], 1, '') '@'];
    l = length(T);
    P = zeros(1, l);
    
    mx = 0; %range
    id = 0; %center
    for i = 2:l-1
        if i < mx
            P(i) = min(P(2 * id - i), mx - i);
        else 
            P(i) = 1;
        end
        
        while T(i+P(i)) == T(i-P(i))
            P(i) = P(i) + 1;
        end
        
        if P(i) + i > mx
            mx = P(i) + i;
            id = i;
        end
    end
    m = max(P)-1;

Java

    // 生成新的辅助String, eg: abc123成为#a#b#c#1#2#3#2#1#
    public static char[] manacherStringString(String str) {
        char[] c = str.toCharArray();
        char[] res = new char[c.length * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            // 两个一样效果, 填充符号"#"
            res[i] = (i % 2) == 0 ? '#' : c[index++];
            // res[i] = (i & 1) == 0 ? '#' : c[index++];
        }
        return res;
    }

    // 返回最长回文串长度
    public static int maxLcpsLength(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] charArr = manacherStringString(str);
        // 辅助回文长度数组, 表示最多能扩充多少
        int[] pArr = new int[charArr.length];
        // 中心点
        int C = -1;
        // 最右边界
        int R = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i != charArr.length; i++) {
            // i在右边界内, i`到C的长度和到i到R的距离, 哪个小, 哪个就是起码成为回文的区域
            // 否则为1, 自身
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            // 检查边界
            while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
                if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) {
                    // 左右字母相等, 扩1, 直到不能扩为止
                    pArr[i]++;
                } else {
                    // 不能扩
                    break;
                }
            }
            // 如果大于R, 那更新回文右边界和中心点
            if ((i + pArr[i]) > R) {
                R = i + pArr[i];
                C = i;
            }
            // 如果需要, 则更新max
            max = Math.max(max, pArr[i]);
        }
        // 返回最大回文长度
        return max - 1;
    }

參考資料

^ Manacher, Glenn. A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String. Journal of the ACM (JACM). 1975-07-01, 22 (3): 346–351. ISSN 0004-5411. doi:10.1145/321892.321896.
^ Apostolico, Alberto; Breslauer, Dany; Galil, Zvi. Parallel detection of all palindromes in a string. Theoretical Computer Science. 1995-04, 141 (1-2): 163–173 [2018-07-03]. ISSN 0304-3975. doi:10.1016/0304-3975(94)00083-u. （原始內容存檔於2020-07-17）.
^ Jeuring, Johan. The derivation of on-line algorithms, with an application to finding palindromes. Algorithmica. 1994-02, 11 (2): 146–184. ISSN 0178-4617. doi:10.1007/bf01182773 （英語）.
^ Gusfield, Dan. Algorithms on Strings, Trees, and Sequences. 9.2 Finding all maximal palindromes in linear time", Algorithms on Strings, Trees, and Sequences. Cambridge: Cambridge University Press. 1997. ISBN 9780511574931. doi:10.1017/cbo9780511574931 （英語）. ^{[失效連結]}

[1] Manacher, Glenn. A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String. Journal of the ACM (JACM). 1975-07-01, 22 (3): 346–351. ISSN 0004-5411. doi:10.1145/321892.321896.

[2] Apostolico, Alberto; Breslauer, Dany; Galil, Zvi. Parallel detection of all palindromes in a string. Theoretical Computer Science. 1995-04, 141 (1-2): 163–173 [2018-07-03]. ISSN 0304-3975. doi:10.1016/0304-3975(94)00083-u. （原始內容存檔於2020-07-17）.

[3] Jeuring, Johan. The derivation of on-line algorithms, with an application to finding palindromes. Algorithmica. 1994-02, 11 (2): 146–184. ISSN 0178-4617. doi:10.1007/bf01182773 （英語）.

[4] Gusfield, Dan. Algorithms on Strings, Trees, and Sequences. 9.2 Finding all maximal palindromes in linear time", Algorithms on Strings, Trees, and Sequences. Cambridge: Cambridge University Press. 1997. ISBN 9780511574931. doi:10.1017/cbo9780511574931 （英語）. ^{[失效連結]}

[1]

[2]

[3]

[4]