manacher 算法學習筆記
學習筆記\({}-\tt manacher\) 算法（馬拉車）
\(\color{red}\xcancel{\small\color{black}\textsf{馬拉車}}\)
\(\small\color{black}\textsf{沒馬拉車}\color{green}\surd\)
問題
求出一個字元串中最長回文串的長度。
暴力
最直覺的思想（霧
枚舉起點，重點，判斷是否回文，總複雜度 \(\mathcal O(n^3)\)
改進
枚舉對稱點，向左右擴散，複雜度 \(\mathcal O(n^2)\)
缺點
- 對稱點可能是一個位置，可能是兩個位置中間，不友善暴力
- 有許多位置被重複搜尋（顯然，本來就是由内向外搜）
manacher
對稱點
對于對稱點不友善的問題，算法的解決方案是 在每兩個位置插入一個相同字元，比如 \(\#\) 或者 $$ $ 或者 \(∼\)。這樣對稱點就會在 原來字元或者新加字元。
同樣，為了防止比對出界，在開頭也要另插入一個字元。
114514
\(\to\)
~~1~1~4~5~1~4~
或
##1#1#4#5#1#4#
比對
事先定義 \(pa_i=\) 以 \(i\) 開頭的回文串的長度。事實上\(pa=\tt Paralindone\)。
對于重複搜尋的問題，算法有兩個輔助變量 \(maxr\) 和 \(mid\)。前者代表 \(\max\{i+pa_i\}\)，後者代表 \(i+pa_i\) 最大時的 \(i\)。
分兩種情況讨論。
情況1 \((i\le maxr)\)
考慮已經算出 \(pa_k(1\le k\lt i)\)，此時我們要求 \(pa_i\)。
\(mid,maxr\) 的位置如圖所示，\(p\) 是 \(maxr\) 對于 \(mid\) 的對稱點，也就是 \(mid-pa _ {mid}\)，\(j\) 是 \(i\) 對于 \(mid\) 的對稱點。
我們找到 \(j\) 以及它的對稱位置：
發現 \(j\) 的左對稱點，已經超過了 \(p\)，可是 \(i\) 的對稱位置會不會超過 \(maxr\) 呢？
不難發現，從對稱部分最右邊開始，可以通過回文兩側相等的性質，一步步傳遞到最左端的青色
那麼 \(s _ {p-1}=s _ {maxr+1}\)，\(maxr\) 應該等于 \(maxr+1\)，是以不可能。
既然當 \(j\) 回文的最左部分超過 \(p\) 時就不可行了，此時答案就為 \(j-p\) 或者 \(maxr-i\)
最後答案 \(pa_i=\min(pa_j,j-p)\)。
為什麼？
- \(pa_j\) 出界，此時 \(pa_j\gt j-p\)，答案 \({}=j-p\)
- \(pa_j\) 未出界，此時 \(pa_j\le j-p\)，答案 \({}=pa_j\)
情況 2 \((i\gt maxr)\)
Code
#include<stdio.h>
#include<string.h>
const int max_n = 1e7 + 1e6 + 1;
const int maxn = 2e7 + 2e6 + 1;
const int& max2(const int& a,const int& b){return a > b ? a : b;}
const int& min2(const int& a,const int& b){return a < b ? a : b;}
char s2[max_n],s[maxn],pa[maxn];
int n;
void chg(){// 處理字元串以友善比對
int now = 0;
s[now] = '#',s[++now] = '#';// 插入從未出現的字元
for(int i = 0;i < n;++i) s[++now] = s2[i],s[++now] = '#';
n = now;
}
void Horseless_pull_car(){// 沒馬拉車
int maxr = 0,mid;
for(int i = 1;i < n;++i){
pa[i] = i < maxr ? min2(pa[mid * 2 - i],pa[mid] + mid - i) : 1;// j-p=maxr-i
for(;s[i + pa[i]] == s[i - pa[i]];++pa[i]);// 一位一位比對
if(pa[i] + i > maxr) maxr = pa[i] + i,mid = i;// 更新 maxr,mid
}
}
int main(){
scanf("%s",s2);
n = strlen(s2);
chg();
Horseless_pull_car();
int res = 1;
for(int i = 0;i < n;++i) res = max2(res,pa[i]);
printf("%d\n",res - 1);// 由于答案是+1存的，是以要-1
return 0;
}