d978: 最长回文字串

2021-05-04 22:17:37 +0800 CST Tags: manacher, palindrome

出處：https://zerojudge.tw/ShowProblem?problemid=d978
提交：https://zerojudge.tw/Submissions?problemid=d978&account=allllllan123456

問題：找到一個由小寫英文字母所組成之字串 (長度可高達 500000) 的最長回文子字串長度。

解法：因為這題原字串的長度很長，一般 $\mathcal O(n^2)$ 的方法肯定行不通，好裡加在我們已經有一個廣為流傳的最快線性 Manacher’s 演算法，直接實作它就可以了！這個演算法主要利用了大回文字串 (簡稱大回文) 內左右鏡射，如果左半邊內以某個字元為中心的最長小回文字串 (簡稱左小回文) 沒有碰到大回文的左邊界，那麼以右半邊的鏡射字元為中心的最長小回文字串 (簡稱右小回文) 長度必等於左小回文長度，這樣子能立刻得到答案的技巧，把時間複雜度壓低。令前面那一句為演算法之基本精神的所屬情況為 case 3，那麼我們還有兩種額外需要修補的狀況沒討論到。如果左小回文已經碰到或超出大回文的左邊界，那麼對應的右小回文也至少要碰到大回文的右邊界，然後還要繼續往右檢查看看這個右小回文能不能再延伸，最後把延伸後的結果設為新的大回文，這個情況是為 case 2。最後一種情況是現在要算的右小回文中心早就超出大回文的涵蓋範圍，那麼我們當然只好重新算過，再把這個右小回文設為新的大回文，這個情況便是 case 1。另外，此算法並無法處理偶長度回文字串，所以一開始必須先在每個字元的左右都安插一個輔助字元 ‘#'，才能確保每次的最長回文子字串長度都是奇數。而且這個算法，每個字元中心的最長回文子字串長度之填表順序，以及大回文右邊界的更新方向都是往右，我們才能確保這個算法的時間複雜度是 $\mathcal O(n)$。

總結來說，我們只需要考慮以下三個 case 即可。(這邊只提供 Case 3 的示意圖)
Case 1: $i > C + R$
Case 2: $i \le C+R\ 且\ i+\text{LPS}[i’] \ge C+R$
Case 3: $i \le C+R\ 且\ i+\text{LPS}[i'] < C+R$
Example image

參考資料：
[1] https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2#Manacher%E7%AE%97%E6%B3%95
維基百科用中文很精煉的點出該演算法的精神以及各種需要考慮的情況，Python 範例程式也非常精簡。
[2] https://josephjsf2.github.io/data/structure/and/algorithm/2020/10/10/manacher-algorithm.html
這篇的解釋非常詳盡，建議先看這一篇培養基本的概念，上面的示意圖也是從這個網站擷取而來。
[3] https://t6847kimo.github.io/blog/2019/05/19/leetcode5-manachers-algorithm.html
這篇把程式的 case 切割得非常好，我上面的 case 切割方式就是參考它的，想自己實作的話推薦這一篇。
[4] http://dino4cat.blogspot.com/2019/06/manacher.html 這一篇也不錯。
[5] https://havincy.github.io/blog/post/ManacherAlgorithm/ 這一篇也不錯。
[6] https://www.jikuai.codes/2020/09/24/manacher-algorithm/ 這一篇只有 code。

實作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


#include <bits/stdc++.h>
using namespace std;

char str[500001];
inline char strI(int i) {
    if (i % 2) return str[i/2];
    return '#';
}

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    int T, LPSr[500000*2+1]; cin >> T;
    while (T--) { int C=-1, R=0, ans = INT_MIN; cin >> str;
        // Example of expanding the string.
        // 0123 --> 01234567
        // abc$ --> #a#b#c#$
        int len = strlen(str) * 2 + 1;
        for (int i=0; i<len; i++) {
            if (i > C+R) {
                R = 0;
                while (i+(R+1)<len && i-(R+1)>=0 && strI(i+(R+1))==strI(i-(R+1))) R++;
                C = i;
                LPSr[i] = R;
            } else if (i + LPSr[2*C-i] >= C+R) {
                R += C - i;
                while (i+(R+1)<len && i-(R+1)>=0 && strI(i+(R+1))==strI(i-(R+1))) R++;
                C = i;
                LPSr[i] = R;
            } else
                LPSr[i] = LPSr[2*C-i];
            if (LPSr[i]>ans) ans = LPSr[i];
        }
        cout << ans << '\n';
    }
    return 0;
}

結果： Example image