Manacher算法学习笔记

Manacher算法是在线性时间内求解最长回文子串的算法。

本文是博主的学习笔记,可能有很多疏漏,不适合作为教程观看。如需教程,可移步UESTCACM 每周算法讲堂 manacher算法,或参考其他更详细的图文资料。

最长回文子串问题

输入一个字符串$s$,输出$s$里最长回文子串的长度。回文串是指$aba$、$abba$、$cccbccc$、$aaaa$这种左右对称的字符串。一个串的子串指此(字符)串中连续的一部分字符构成的子(字符)串。

朴素的求解方法

这里可以想到这样几种求解方法:

  • 暴力枚举枚举左右端点的方法所有连续子串,再判断所有枚举出的字串是否是回文串,如果是则与当前最长的那个进行大小比较,由于枚举左右端点是$O(n^2)$的,判断是$O(n)$的,这个算法的复杂度是$O(n^3)$的。
  • 暴力枚举回文串的中点,从中点向两边扩展,这样可以保证拓展出来的串一定是回文串,将当前位置拓展出的回文串的长度与当前最长的进行大小比较,时间复杂度$O(n^2)$。
  • 预处理字符串的前缀哈希和后缀哈希,依旧暴力枚举回文的中点,但是对于每个中点用二分的方法来拓展,将当前位置拓展出的回文串的长度与当前最长的进行大小比较,时间复杂度$O(n \log n)$。

以上的求解方法中,前两种前两种只能应付字符串长度比较小的情况,而第三中可能出现哈希冲突,下面介绍线性时间内求解最长回文子串的方法。

Manacher算法

首先为了方便,我们在每对相邻字符中间插入$\#$得到新的字符串,用$f_i$表示新的字符串的第$i$位为中心,可拓展出的最大回文半径(这个半径包涵$i$),这样可以保证找到的回文串都是奇数长度的,那么$f_i – 1$就是每个点为中心最大回文串的长度。

由此可知,Manacher依旧需要暴力枚举每一个点,并假设这个点是回文中点。考虑假设我们已经计算完$[1,i-1]$中所有的$f_i$,也就是我们已经知道每个点作为回文中点的时候的最大回文半径$r_i$,那么我们也就自然知道了$i$为中心最大回文的右端点$f_i + 1 – 1$。Manacher算法需要我们维护当前求到的最大回文字串的中心点$i_m$以及右端点$r_{i_{m}}$。假设当前这个点$i$小于等于$r_{i_{m}}$,那么这个点被包含在$i_m$为中心的最长回文字串内,它一定存在一个关于$i_m$的对称位置$j$,$f_j$是已经计算过的,那么此时先令$f_i = \min \{ f_j, i_m + r_{i_m} – 1\}$,否则我们暂令$f_i = 1$。那么现在的$f_i$表示以$i$为中心的最长回文字串长度的下界,因为我们当前只能知道$i$到$i + f_i – 1 $这一段,并不知道后面的字符能否被扩展到当前$f_i$记录的字串当中来。

为了知道后面的字符能否被扩展到当前$f_i$记录的字串当中来,我们继续暴力枚举它的半径,从已经得到的$f_i$开始,扩展得到最大的$f_i$。这个时候我们维护当前求到的最大回文字串的中心点$i_m$以及右端点$r_{i_{m}}$。

代码

这里以51Nod 1088为例。

 

1
说点什么

avatar
50
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
0xfaner Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
0xfaner
游客
0xfaner

马拉车!tql