Manacher算法是什么
Manacher算法就是马拉车。
Manacher算法就是用于解决回文子串的个数的。
问题引入
题目大意
给出一个只由小写英文字符 (texttt a,texttt b,texttt c,ldotstexttt 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}+1le 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) 的前一个点，而可能是在 (1sim i) 中的一个点。
想象一下，当出现第二种情况时，(i+1) 就必须要用 (O(n)) 来暴力得到 (p_{i+1})，但是如果 (p_{i+1}) 覆盖了整个 ([1,n]) 的话，后面的 (i+2sim 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;
}
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
