以往我是不太爱学算法的,尤其是这种适用面很狭窄的算法,因为总感觉算法这东西学了也不一定考,考了也不一定能A。不过最近刷题的时候发现,自己经常遇到的一些题,虽然和我学过的算法没什么关系,但是代码技巧和思维技巧,明明就是我学XX算法的时候的思路嘛。再加上我最近的代码能力有所增强,看新算法、学新算法的时间我感觉明显缩短,理解力up↑up↑。于是开始喜欢看新算法了。
据说这个算法赛场上很难有机会用到,因为适用面狭窄。
关于最大回文串的匹配,常见的算法有两种: 1. 用\(O(n^2)\)的时间复杂度,暴力枚举每一个子串。再对于每一个子串,用\(O(n)\)的复杂度去判断他是否是一个回文串。总时间复杂度为\(O(n^3)\)。 2. 用\(O(n)\)的时间复杂度去枚举中轴,对于每一个中轴,用\(O(n)\)的时间复杂度去向两边扩展。总时间复杂度为\(O(n^2)\)。(注意,这种方法对于偶数中轴和奇数中轴会有一些不一样的情况需要考虑。)
Manacher(马拉车)算法
这种算法可以看做是上面第二种算法的一个改进(成电视频中认为这是一个剪枝)。 对于第二种算法,如果当前匹配GG了,那么下一次匹配,依然要从\(1\)(或\(0\))开始重新去检查回文串。
然而,回文串里面有大量相似和冗余的信息,我们希望能用回文串本身的一些性质和所包含的信息,去避免每次都要从头开始匹配的问题。
首先,我们需要对串本身进行一些改进,以避免第二种算法对于奇数和偶数需要分开判断的情况。我们在串的每个字母前后都加入特殊字符#
,如对于aaa
来说,改变后串为#a#a#a
。
接下来我们约定四个变量表示: 1
2
3
4Ma[i] // Ma表示改进后串,Ma[i]表示第i个字符
Mp[i] // 表示从第i个字符开始向两边延伸,最多可以延伸Mp[i]位(他们都是回文串)。
Mx // 表示之前延伸过的所有回文串,所到达过的最右端。
Id // 表示Mx所对应的回文串的中心。
首先我们初始化:$Mx = 0 , Id = 0 $ 接下来我们和第二种算法所做的基本一样,枚举中轴: 1
2// 为缩减代码,这里使用strlen函数,实际使用中请务必注意。
for( int i = 0 ; i < strlen(Ma) ; i++ )
分类讨论
情况1 Mx > i
那么如果我们枚举中发现\(Mx > i\),便可以说明,之前肯定有某一个串,曾经更新覆盖过\(i\),我们能否利用对称的性质,使\(i\)能有一个比较大的初始值,然后再进行常规操作。
由\(Mx > i\) ,我们可以知道显然有\(Mx > i > id\),那么既然\(Mx\)和\(Mx'\)对称,中轴\(id\)知道,那么\(i\)和\(i'\)也一定会对称。 这是这个算法的核心。 \(i'\)的坐标是多少呢?就是\(2 * id - i\) 由 \(id - ( i - id )\)得到 。
情况(1) i和i'都在Mx与Mx'内
那么我们是不是可以直接使用 \(Mp[i] = Mp[ 2 * id - i ]\)呢? 在\(i\)和\(i'\)都在\(Mx\)和\(Mx'\)内时,这是正确无误的。
但是还有另外一种情况。
情况(2) i'在Mx'外
当\(i'\)很长,延伸到了\(Mx'\)外时,我们并不能保证\(i\)也能一如既往的延伸到\(Mx\)以外。这时候我们只能保证\(i\)在\(Mx\)以内的时候,是对称的。 所以这时候 \[Mp[i] = Mx - i\]
情况(1)和情况(2)
我们并不关心具体是什么情况,因为这对时间复杂度没有影响。所以我们只要Mp[i] = min( Mp[2*id-i] , Mx - i )
就足够了。
情况2 Mx <= i
遇到这种情况我们怎么办呢?老老实实的去扩展吧。但是在这里我们可以一边扩展,一边去更新Mp[i]
的值。 1
while( Ma[ i + Mp[i] ] == Ma[ i - Mp[i] ] ) Mp[i]++;
这样即就是一遍扩展,一遍更新了。
Manacher完整实现
最后,我们把上面这几部分组合一下,并注意更新\(Mx\)和\(Id\)的值,就可以了。
1 | for( int i = 0 ; i < size ; i++) |
最终第i个字符的回文串长度为\(Mp[i] - 1\) ## 时间复杂度
这个时间复杂度不是特别好算,我们可以使用摊还分析。具体可以参考一下其他量化分析文章,会很详细。简单的理解可以是: 发现\(Mx\)每次最少往右移动\(1\),并且除此之外其他的不会对复杂度有贡献。
遇到的一些问题
- 理解为何\(Mp\)数组只是记录了向其中一边延伸的问题,却可以做最终答案: 因为#号的存在,使得两边的#号必然相等,那么,一边就可以看做是两边了。
- 需要正确理解为什么第i个字符的回文串长度需要\(-1\): 同样因为#的存在,当以#为中心,需要去除中心的#,当以非#为中心,需要去除相邻的一个#。
- 边界等问题。(有些地方会把开头加一些其他的特殊字符以避免边界问题。目前这类问题我还没有遇到)
参考资料
- 电子科技大学-字符串算法选讲 (昨天很多博客没看清楚,看了这个半个小时就会了)
- 有什么浅显易懂的Manacher Algorithm详解 - 知乎 (和第一个一起使用)
- O(n)回文子串(Manacher)算法
- 如何证明Manacher算法的时间复杂度是O(n)