Manacher演算法是什么
Manacher演算法就是馬拉車，
Manacher演算法就是用于解決回文子串的個數的，
問題引入
P3805:【模板】manacher 演算法
題目大意
給出一個只由小寫英文字符 \(\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z\) 組成的字串 \(S\) ,求 \(S\) 中最長回文串的長度，
演算法
記錄
為了找到最長的回文串的長度，我們首先就要考慮如何去把每一個回文串表示出來，
因為是回文的，所以我們可以用 \(p_i\) 來表示，
其中 \(i\) 表示回文串的中心，\(p_i\) 表示以第 \(i\) 個字符為中心的回文串的最長的回文串的半徑，
但是這樣我們只能表示奇數長度的回文串，而偶數回文串就不能解決，
演算法推到
但是一個 \(S\) 的回文串個數最壞可能是 \(n^2\) 級別的，會 TLE，
那么我們該如何快速得到每個以 \(i\) 為中心的最長的長度呢？
就像做 DP 題目一樣，考慮類似 DP 的轉移，
考慮如何通過 \(p_i\) 來得到 \(p_{i+1}\)，
我們用一幅圖來生動形象的體會一下：
這里我們就可以清晰的看到通過 \(p_i\) 得到 \(p_{i+1}\) 的兩種，
- 當 \((i-1)-q_{i-1}+1>i-q_i+1\) 時，即以 \(i-1\) 為中心的回文串被 \([i-p_i+1,i+p_i-1]\) 所包含在內，
- 當 \((i-1)-q_{i-1}+1\le i-q_i+1\) 時，即以 \(i-1\) 為中心的回文串并沒有被 \([i-p_i+1,i+p_i-1]\) 所包含在內，
第一種情況是很好辦的，因為 \(i+1\) 與 \(i-1\) 以 \(i\) 為中心對稱，直接 \(p_{i+1}=p_{i-1}\)，
但是第二種情況就不好解決了，因為這就意味著我們似乎是要在繼續判斷 \(p_{i+1}\) 的最大值，好像如果運氣不好的話時間復雜度就會達到 \(O(n^2)\)，
這時就需要考慮單調性了，\(i\) 就可以不是 \(i+1\) 的前一個點，而可能是在 \(1\sim i\) 中的一個點，
想象一下，當出現第二種情況時，\(i+1\) 就必須要用 \(O(n)\) 來暴力得到 \(p_{i+1}\)，但是如果 \(p_{i+1}\) 覆寫了整個 \([1,n]\) 的話，后面的 \(i+2\sim n\) 就都會被 \(p_{i+1}\) 所覆寫了，
即可以直接 \(O(1)\) 得到答案，時間復雜度也就是 \(O(n)\)，
所以我們可以得到結論，Manacher 的時間復雜度具有單調性，是單調不下降的，
實作
為了確保它的單調性，我們就需要一個 \(mid\) 來記錄回文覆寫最大的點的下標，\(mx\) 為 \(mid\) 回文串的左端點，
\(p_i\) 的初始值就是:
在判斷 \(a_{i+p_i}\) 是否與 \(a_{i-p_i}\) 相同，相同就擴張 \(p_i\)，
然后在嘗試用 \(i\) 去更新 \(mid,mx\) 就可以了，
Code
#include<bits/stdc++.h>
#define N 12000005
#define int long long
using namespace std;
int n,mx=1,mid,ans,p[N<<2];
char a[N<<2],s[N<<1];
signed main(){
cin>>s+1;
n=strlen(s+1);
a[0]='$';
a[1]='#';
for(int i=1;i<=n;i++)
a[i<<1]=s[i],
a[(i<<1)+1]='#';
n=(n<<1)+2;
a[n]='@';
for(int i=1;i<=n;i++){
if(i<=mx)p[i]=min(mx-i+1,p[mid*2-i]);
else p[i]=1;
while(a[i+p[i]]==a[i-p[i]])++p[i];
if(i+p[i]>mx)mx=i+p[i]-1,mid=i;
ans=max(ans,p[i]);
}
cout<<ans-1;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/555554.html
標籤：其他
上一篇：前端學習C語言 - 函式和關鍵字
下一篇：返回列表