是从最近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 为中心的回文子串中）。但是在这个基础上，我们可能可以继续扩充——继续枚举检验两边的字符是否相同，如果相同则可以扩展。
枚举完为止~
看起来马拉车算法局限性比较强，但实际上可以在回文串的限制上有很多变化——甚至加上一些单调栈、线段树之类的优化！至于具体哪些地方可能会用其他的算法我会在模板代码里注释出来。
『例题』
（也可以是 URAL - 1297，只是一个输出具体的子串，另一个只输出长度）
如果原串是从0开始存储的话，我们可以在 Manacher 中算得 haf 的最大值 resmax，以及它对应的中心位置 resmid —— 略找规律，我们可以发现在原串中，这个回文子串起始于 $(resmid-resmax)/2$，长度为 $(resmax-1)$
我的思路大概就是先预处理出 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];
int Manacher(string str){
string mdy="-+";
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++){
if(i<Rig) haf[i]=min(haf[Id*2-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;
}
}
|
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
|
#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
|
#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 ； ↩