学习笔记 - Manacher算法

是从最近Codeforces的一场比赛了解到这个算法的~
非常新奇,毕竟是第一次听说 $O(n)$ 的回文串算法
我在 vjudge 上开了一个〔练习〕,有兴趣的reader们可以参考一下 $QwQ$


『算法简述』

一个思路比较简单但非常有效的字符串算法(其实不止字符串,反正就是用来求回文的),用于求给定字符串中的回文子串,有一些研究者证明了它的时间复杂度均摊下来是 $O(n)$ 的,只可惜我看不懂他们怎么证明的……
中文名叫“马拉车”算法(或许是音译过来的),它的想法非常简单,只是利用了之前求解到的回文串。

首先我们需要对原字符串str进行一个操作——假如原串是 $str=s_0s_1s_2…s_l$,那么我们定义两个不同的元素 $a,b$ ,且 $a,b$ 不等于任何一个 $s_i$。那么我们把原串改成 $mdy=abs_0bs_1bs_2b…bs_lb$,可以发现 $mdy$ 中若存在回文子串,那么回文子串的长度一定是奇数1,这样会方便一点。可见修改过后字符串的长度变成了 原长2+2;但是要注意我们一般都*把数组设置为从0开始

接下来我们定义 haf[i] 表示以 i 为中心的回文串的最长半径,比如 “abcba” 的haf[2]=3。这样我们就可以表示一个以i为中心的最长的回文子串了!

下面就是马拉车算法的精华——定义 $Rig$ 为当前找到的回文子串中右端点的最大值,$Id$ 为 $Rig$ 对应的回文子串的中心位置。
我们枚举回文子串的中心位置 i ,如果 i<Rig ,那么 i 就一定被包含在一个回文子串里2,那么我们找到 i 关于 Id 的对称位置即 $j=(2Id-i)$ ,*可以算出以j为中心的被包含在以Id为中心的最大回文子串中的最大子串长度(我知道说起来有一点晕,但是相信 reader 们看了例子就会明白),举个例子:

原串为 “1323141323” ,现在 i=8 ,那么 Rig=9,Id=5(对应的子串为 “323141323”)
找到对称位置 j=2 ,找到以 j 为中心的包含在 “323141323” 中的最大回文子串 “323” (不能是 “13231”,因为左边的 “1” 在 “32314323” 外

那么我们可以知道因为 i,j 关于 Id 对称,所以以 i 为中心的回文子串的半径至少是 min(haf[j],Rig-i)(取min是为了限制找到的串在以 Id 为中心的回文子串中)。但是在这个基础上,我们可能可以继续扩充——继续枚举检验两边的字符是否相同,如果相同则可以扩展。

枚举完为止~

看起来马拉车算法局限性比较强,但实际上可以在回文串的限制上有很多变化——甚至加上一些单调栈、线段树之类的优化!至于具体哪些地方可能会用其他的算法我会在模板代码里注释出来。


『例题』

一、〔HDU 3068 - 最长回文〕

(也可以是 URAL - 1297,只是一个输出具体的子串,另一个只输出长度)
如果原串是从0开始存储的话,我们可以在 Manacher 中算得 haf 的最大值 resmax,以及它对应的中心位置 resmid —— 略找规律,我们可以发现在原串中,这个回文子串起始于 $(resmid-resmax)/2$,长度为 $(resmax-1)$

二、〔HDU 4513 - 完美队形II 〕

我的思路大概就是先预处理出 low[i] 表示以 i 为结尾的最长的不下降子串的长度(不是序列!必须连续!),然后找出以当前位置为中心的最长回文串,再判断回文子串中的左半部分的不下降长度,相应的,子串的右半部分就是不上升的了~


『源代码』

模板代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int haf[LEN*2+10]; //LEN是原串的长度
int Manacher(string str){
string mdy="-+"; //a='-' , b='+'
for(int i=0;i<str.length();i++)
mdy+=str[i],mdy+='+';
int Rig=0,Id=0;
for(int i=1;i<mdy.length();i++){ //注意这里从1开始,忽略开头的'-'
if(i<Rig) haf[i]=min(haf[Id*2-i],Rig-i);
else haf[i]=1; //i本身构成一个回文子串
while(mdy[i-haf[i]]==mdy[i+haf[i]]){
haf[i]++;
/*
这里经常会进行一些其他操作;
*/
}
if(i+haf[i]>Rig) Rig=i+haf[i],Id=i;
/*
这里存储答案;
这里也经常进行其他操作;
*/
}
/*
求解完回文子串后可能还要处理一些东西~
*/
}

HDU 3068 - 最长回文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*Lucky_Glass*/
#include<bits/stdc++.h>
using namespace std;
const int SIZ=110000*2;
char str[SIZ+5],mdy[SIZ*2+5];
int haf[SIZ+5];
int Manacher(){
mdy[0]='-';mdy[1]='+';
int lenstr=strlen(str);
for(int i=0;i<lenstr;i++)
mdy[2*i+2]=str[i],mdy[2*i+3]='+';
mdy[2*lenstr+2]='$';
int reslen=0,resmid,Rig=0,Id=0;
for(int i=1;i<lenstr*2+2;i++){
if(i<=Rig) haf[i]=min(haf[2*Id-i],Rig-i);
else haf[i]=1;
while(mdy[i-haf[i]]==mdy[i+haf[i]]) haf[i]++;
if(i+haf[i]>Rig){
Rig=i+haf[i];
Id=i;
}
if(reslen<haf[i]){
reslen=haf[i];
resmid=i;
}
}
return reslen-1;
}
int main(){
while(~scanf("%s",str)){
printf("%d\n",Manacher());
}
return 0;
}

HDU 4513 - 完美队形II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*Lucky_Glass*/
#include<bits/stdc++.h>
using namespace std;
const int N=100000;
int Cas,n;
int hgt[N+5],mem[N*2+5],low[N+5],haf[N*2+5];
int Manacher(){
int Rig=0,Id,ret=0;
for(int i=1;i<n*2+2;i++){
if(i<Rig) haf[i]=min(Rig-i,haf[Id*2-i]);
else haf[i]=1;
while(mem[i-haf[i]]==mem[i+haf[i]]) haf[i]++;
if(i+haf[i]>Rig){Rig=i+haf[i];Id=i;}
int len=haf[i]-1,mid=i;
int lef=(mid-len)/2+1;len;
if(len&1){
int fhaf=len/2,fmid=lef+len/2;
fhaf=min(fhaf,low[fmid]-1);
ret=max(ret,fhaf*2+1);
}
else{
int fhaf=len/2,fmid=lef+len/2-1;
fhaf=min(fhaf,low[fmid]);
ret=max(ret,fhaf*2);
}
}
return ret;
}
int main(){
scanf("%d",&Cas);
for(int cas=1;cas<=Cas;cas++){
memset(mem,0,sizeof mem);
memset(low,0,sizeof low);
scanf("%d",&n);
mem[0]=-1;mem[1]=-2;
for(int i=1;i<=n;i++){
scanf("%d",&hgt[i]);
if(hgt[i-1]<=hgt[i]) low[i]=low[i-1];
low[i]++;
mem[i*2]=hgt[i];mem[i*2+1]=-2;
}
printf("%d\n",Manacher());
}
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~

1. 简单的举个例子:$str=abba$,假设 $a=’@’,b=’|’$,那么修改过后的字符串就是 $mdy=@|a|b|b|a|$,可见任意一个回文子串(例如 $|b|b|$)都是奇数的长度;
2. 其实这里隐含了一个条件:Id<i,因为 Id 是在枚举到 i 之前计算出来的,所以一定小于 i ;
0%