Manacher 算法

Manacher 算法

Manacher 算法可以用来求最长回文子串。

求最长回文子串有O(n^3)O(n^2)的两种浅显易懂的算法

算法一O(n^3):枚举子串的首尾,再判断是否是回文子串

算法二O(n^2):枚举子串的中点(长度为偶数的串枚举中间的两个点), 从中点向外扩展,一旦不是回文子串,直接从下一个中点开始扩展

然而当n变的很大时,这两种算法的效率难以接受

长度的奇偶性

算法二需要考虑奇偶性,处理比较麻烦,所以在这里有一个技巧:在字符串首尾以及两两字符间插入一个符号,这里用#

举例

abba -> #a#b#b#a#

这样原来的每一个回文子串都变为长度为奇数的带#的回文子串

重复解决的子问题

可以发现,在算法二中有许多问题是重复的

举例(这里未处理过的串)

char : a b a b a

i    : 1 2 3 4 5

i=4时,会枚举到右边的子串aba,但是当i=3时已经知道ababa是回文串,而当i=2时可知ababa的左边aba是回文串,所以ababa的右边相同长度的子串aba也是回文串

我们记录一个数组RLRL[i]表示以i为对称轴的回文子串的左右端点到i的距离

再需要两个辅助的变量maxright表示所有回文子串能到达的最右的端点,pos表示maxright对应的回文子串的对称轴

设现在对称轴枚举到ii肯定大于pos

i'maxright'分别为imaxright关于pos的对称点

1)i<=maxright

如图

1'以i'为对称轴的回文串左端不在maxright'左边

如图

 

 

显然RL[i]=RL[i'],所以令RL[i]=RL[i']

2'以i'为对称轴的回文串左端在maxright'左边

如图

 

i为对称轴能够确定是回文串部分只有一部分,此时令RL[i]=maxright-i,其实这里已经不能继续扩展了,因为如果可以继续扩展的话,那么以pos为对称轴的回文串应该更长

2)i>maxright

如图

现在就没办法了,只能令RL[i]=0,然后继续扩展

代码实现

时间复杂度

由上面可以得出

1.RL[i]=maxright-i||RL[i]=RL[2*pos-i]时,不可以再扩展,RL[i]可以在O(1)的时间里确定,

2RL[i]=0时,扩展的过程中i+RL[i]maxright一直向右移,然后又会更新maxright,因为每次更新maxright只会向右,不会向左,所以所有while语句总的时间复杂度是O(n)

所以Manacher 算法的复杂度为O(n)

参考资料

https://www.zhihu.com/question/30226229

https://segmentfault.com/a/1190000003914228

http://www.61mon.com/index.php/archives/181/

https://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/

One thought on “Manacher 算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注