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/

Manacher 算法
Tagged on:     

6 thoughts on “Manacher 算法

  • 2017年6月27日 at 上午3:49
    Permalink

    This is very interesting, You're an overly professional blogger.
    I've joined your rss feed and stay up for in the hunt for more
    of your great post. Also, I have shared your website in my social networks

    Reply
  • 2017年7月21日 at 上午7:52
    Permalink

    After exploring a few of the blog articles on your site, I
    honestly like your way of blogging. I book-marked it to my bookmark
    site list and will be checking back in the near future. Please check out my
    web site as well and tell me what you think.

    Reply
  • 2017年7月21日 at 上午8:09
    Permalink

    I go to see day-to-day a few blogs and websites to read content,
    except this web site offers quality based articles.

    Reply
  • 2017年8月31日 at 上午4:51
    Permalink

    I for all time emailed this weblog post page to all my contacts, because if like to read it next my links will
    too.

    Reply

发表评论

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