是从最近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 | int haf[LEN*2+10]; //LEN是原串的长度 |
HDU 3068 - 最长回文
1 | /*Lucky_Glass*/ |
HDU 4513 - 完美队形II
1 | /*Lucky_Glass*/ |
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 ; ↩