Manacher算法笔记

2019-11-14 13:02:52

字体：大中小

来源：转载

供稿：网友

定义：

一种简单的寻找回文子串的算法。可以在O(N)的时间复杂度内，求出以每个字母为对称中心的回文子串。

属于奇技淫巧？回文串的题很少啊。我们还有后缀数组求回文子串的方法，可以做到O(Nlog2N) $O(Nlog_2N)$ ，但是写起来烦，(主要是我不会写)。

模板

#define min(a,b) ((a)<(b)?a:b)void Manacher(char *a) { int MaxId,id; for(int i=1;a[i]!='/0';i++) { if(MaxId>i) p[i]=min(p[2*id-i],MaxId-i); else p[i]=1; while(a[i+p[i]]==a[i-p[i]]) p[i]++; if(p[i]+i>MaxId){ MaxId=p[i]+i; id=i; } } }/*以下是构造的片段*/for(i=1;b[i]!='/0';i++) { a[i<<1]=b[i]; a[(i<<1)+1]='#'; }a[0]='?',a[1]='#';n=(i<<1)+2,a[n]=0;

说明

定义一些符号：

原串:S0 $S_0$ 处理后保证奇数长度的串:S $S$ 反串:S′ $S'$ (即为S $S$ 前后倒置的串) 数组:P $P$ 记录以每个字符为中心的最长回文半径的数组(最小为1，即只含有其本身)

预处理

将S0 $S_0$ 两个两个字符之间插入不属于原字符集的字符，将其转化为S $S$ 。

引理

P[i]−1 $P[i]-1$ 是以Si $S_i$ 为中心的回文子串在原串中的长度。

算法

我们接下来还要再定义两个数字，即：

MaxId $MaxId$ 为之前的回文串中匹配到的最远位置 id $id$ 就是MaxId $MaxId$ 被取到时的i $i$ 点

对于i′=2∗id−i $i'=2*id-i$ ，容易看出i′ $i'$ 和i $i$ 关于id $id$ 对称。但如果这一部分的回文串，翻过去超出了MaxId $MaxId$ ，那我们就不能保证原有的对称性。那么为了保证正确性，我们在这两种可能性中取最小，最终我们有P[i]=min{P[2∗id−i],MaxId−i} $P[i]=min/{P[2*id-i],MaxId-i/}$ 。但此时的P[i] $P[i]$ 不是最佳解，而只是最小值。我们通过迭代，可以求到P[i] $P[i]$ 的最优解。最终统计时，统计P $P$ 数组的最大值即可。

HDU3068

裸题。 (也没什么好题了)

#include <stdio.h>#define M 110010char b[M],a[M<<1];int p[M<<1];#define min(a,b) ((a)<(b)?a:b)#define max(a,b) ((a)>(b)?a:b)int main() { int i,n,id,MaxL,MaxId; while(scanf("%s",b+1)!=EOF) { MaxL=MaxId=0; for(i=1;b[i]!='/0';i++) { a[i<<1]=b[i]; a[(i<<1)+1]='#'; } a[0]='?',a[1]='#'; n=(i<<1)+2,a[n]=0; for(i=1;i<n;i++) { if(MaxId>i) p[i]=min(p[2*id-i],MaxId-i); else p[i]=1; while(a[i+p[i]]==a[i-p[i]]) p[i]++; if(p[i]+i>MaxId) { MaxId=p[i]+i; id=i; } MaxL=max(MaxL,p[i]); } PRintf("%d/n",MaxL-1); } }

上一篇：try-catch以及try-catch-finally

下一篇：蓝桥杯回文数

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注