Manacher算法详解

2019-11-06 08:12:31

字体：大中小

来源：转载

供稿：网友

Manacher算法详解

RT，Manacher算法今天第一次写，有不少细节，也容易写错，下面进行一个小小的总结

原理

首先，我们应该已经看到过很多有关回文串的题目了，当我们不会Manacher的时候，我们往往是用~~回文自动机~~后缀数组代替的，这时候我们会发现有些题它并不能卡过，因为后缀数组是O(nlogn) $O(nlogn)$ 的，而且编程复杂。这时候我们就需要Manacher算法，它是一个O(n) $O(n)$ 的算法，而且编程简单

它的主要思想是先将奇偶回文串情况讨论的部分去掉，我们可以通过在每个字符间，包括开头与末尾，插入特殊字符来达到这一点

然后，我们通过扩展KMP的思想，建立一个最远指针，它表示当前的回文串最远达到的地方，这时我们就可以利用回文的性质来加速，求出一个数组f $f$ ，它表示以i $i$ 为中心的回文串的半径。由于最远指针最多被推动n次，所以Manacher的复杂度是O(n) $O(n)$

代码

下面是代码

#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#define maxn 200005using namespace std;int f[maxn],len1,PRe[maxn*2],suf[maxn*2],len;char txt[maxn],s[maxn*2];void Manacher(){ for(int i=0;i<len1;i++){ s[i<<1]='@'; s[(i<<1)+1]=txt[i]; } s[(len1)<<1]='@'; len=2*len1+1; int mx=0,p=0; for(int i=0;i<len;i++){ if(mx>i) f[i]=min(mx-i,f[2*p-i]); else f[i]=0; while(i+f[i]+1<len&&i-f[i]-1>=0&&s[i+f[i]+1]==s[i-f[i]-1]) f[i]++; if(f[i]+i>mx){ mx=f[i]+i; p=i; } } return;}int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); while(scanf("%s",txt)==1){ len1=strlen(txt); Manacher(); int k=0,op=0; for(int i=0;i<len;i++){ if(i&1) f[i]=((f[i]>>1)<<1)+1; else f[i]=((f[i]+1)>>1)<<1; k=max(k,f[i]); } printf("%d/n",k); } return 0;}

它的作用是每次求出一个字符串的最长回文子串

细节

总结一下

1.起点与终点都要插入特殊字符

2.输出时要考虑奇偶情况，即注意转换回原串回文串时的处理，注意不要先求k $k$ 的最大值，最后再处理k $k$

3.数组要足够大