找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6497|回复: 6
收起左侧

[精选刷题题目讨论帖] 线性时间求最长回文子串——Manacher算法

[复制链接]
发表于 12-14-2014 10:42 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-28-2014 02:18 PM 编辑

Manacher算法——求最长回文子串。线性时间最长回文子串算法
初始此算法,我折服于其简单优雅。思索了几天本文如何写,我还是决定把它写出来,和大家分享。
我们亲切地称此算法为“马拉车算法”。
问题就是求一个字符串S的最长回文子串。
(1) 暴力解法, 枚举起点i,枚举终点j,判断回文。 三个复杂度都是O(n),由于嵌套——总复杂度O(n^3)
(2)所谓dp,  我感觉这个问题所谓dp,有点生搬硬套之嫌。bool dp【i】[j] 表示i..j是否是回文的。(i <= j)。 我们看一下dp【i】【i】 = true, dp【i】[i + 1] = (s【i】 ==s[i + 1]) 一般的j >= i + 2, dp【i】[j] = (s【i】 == s[j]) && dp[i + 1][j - 1],  我们打出这张表,顺便找间隔最大的j就可以了。 时间O(n^2), 空间O(n^2)。
(3) 我们真的需要O(n^2)空间么?回文串必然存在“对称点“,那么我们可以枚举对称点,即回文串的中心,从中心往两边扫,看一下是否对应的字符相等,这样我们求出了以每个点为中心的最长回文串长度。枚举中心 O(n),扫描O(n),所以时间是O(n^2),但空间是O(1)的。注意,由于回文串长度可能是奇数或者偶数,所以中心的位置可能是一个实际的字符,也可能是“两个字符之间”,这个要小心处理。
(4)Manacher算法
思路是和(3)类似的,我们试图求出以每个点为中心的最长回文子串的长度,这个最大值,显然就确定了最长的回文子串。
(a) 处理奇数长度和偶数长度
鉴于(3)里面处理长度复杂,我们给s每个字符两边都加上一个不在原来串里的特殊字符,例如'#',必须保证这个字符不在字符串里出现,如果所有字符都在字符串里出现,建议把字符串当作int数组处理,因为范围扩大了,总会有一个int不在原始字符串中……
例如,原始字符串aba, 处理后就变为,#a#b#a#,这样的好处是,回文串的中心肯定是某个字符,要么是原始串的字符,要么是# (对应中心在两个原始串两个字符之间)。
(b) 记录一些东西—— p数组。
这个算法最关键部分是记录p数组,p【i】表示以i为中心的最长回文子串可以延伸的长度,也就是说字符串在[i - p【i】, i + p【i】]是回文的,并且是以i为中心最长的。即[i - p【i】 - 1, i + p【i】 + 1] 就不回文了(或者越界了)
#a#b#a#
对应的p[] = {0,1,0,3,0,2,0}, (a)巧妙之处在于p[]的定义对应了原始串每个位置为中心的最长回文子串的长度,#表示原始字符串两个字符之间。
我们为什么要O(n)空间保存p数组?显然,p【i】和更早的值有关,这个是关键。
我们要计算p【i】时,对0<=j
对于每个p[j],由定义[j - p[j], j + p[j]] 实际上定义了一个框,这个框里的串是回文的。我们记录一个右边界尽可能靠右的框,即记录一个之前算过的位置C,满足0 <= C < i, 并且C + p[C]最大。
如果C + p[C] >= i ,那么我们很幸运,这个框包括了字符i,我们可以利用之前的结果,




上图来自leetcode的论坛,我们要算p[13],之前算得右边界最大的框是C = 13的框,因为i在框里,我们得到i关于C的对称点是i' = 9,p[9] = 1, 我们发现p[13] + 1也在框里,可以立刻得到p[13] = 1,这时因为9和13的情形完全一样。
但这不是全部,再来看一个例子:




和上一个类似,目前最大框是C = 11的框,i = 15还是在框里,i关于C的对称点i' = 7, p[7] = 7, 我们发现15 + 7 = 22,我么能能否说p[15] = 7呢? 显然不能,因为22超出了框的范围,我们只能说p[15] >= 5, 也就是说框住的东西,我们完全知道,没框住的东西我们一无所知。
综合上述两种情况,我们能够得到p【i】 >= min(p[i'], R - i)  (R是框的右边界),如果p[i'] >= R - i,那么p【i】是有可能比R - i更大的。怎么办——暴力比较!我们继续比较i - p【i】和i + p【i】。


还有一种更极端的情况,就是C + p[C] < i, i根本不在矿里,这时我们也只能暴力比较了。


注意我们要维护框,所以每次暴力比较之后,都要把C更新为现在的i。


核心代码:


[code]string s = "#";
    for (int i = 0; i < S.length(); ++i) {
        s += S【i】;
        s += "#";
    }
    int n = s.length();
    int center = 0, right = 0,answer = 0;
    vector p;
    p.resize(n);
    for (int i = 0; i < n; ++i) {
        int ii = (center << 1) - i;
        for (p【i】 = (i < right)?min(p[ii], right - i):0; (i - p【i】 - 1 >= 0) && (i + p【i】 + 1 < n) && (s[i - p【i】 - 1] == s[i + p【i】 + 1]); ++p【i】)
        ;
        if (i + p【i】 > right) {
            right = i + p【i】;
            center = i;
        }
    }[/code]关于算法复杂度:
显然外层i循环了n次。 关键是内层p【i】的循环次数,前面已经讲到,只有框不住的时候(不管是开始就没框住,还是p[i']太大),才会有++p【i】这种操作,而且这时候最终一定会执行rihgt = i + p【i】, center = i,这是因为现在的框右边界更靠右了。
也就是说:
(1) 框住的时候, O(1)得到p【i】。
(2) 框不住的时候, 线性得到p【i】 并且right = i + p【i】, 这里的关键是right增加的量和++p【i】的次数是相同的。就是说在框外的部分p【i】每加1,最终框的右边界就往右移动1。
而right最终也就到达2n - 1,所以right增加的次数是线性的,也就是说所有p【i】执行++的次数是O(n)的,所以两个循环执行的总次数是O(n)的。
应用拓展:
(1) 求所有回文子串的个数?
Manacher其实告诉了我们所有可能的回文子串,比如p【i】 = 5,实际上是说以i为中心有长度为1,3,5的回文子串。所以其实累加(p【i】 + 1) / 2就是总格数了(奇数偶数统一处理,除以2是下取整的。)
(2) 在一个字符串开头加入多少个字符,能把字符串变成回文的?
其实是要计算包含开头的最长回文子串长度,然后用原串长度减去这个长度,就是在开头要加入的字符数,保证和尾端那些也构成回文。
前已述及,我们都可以得到所有回文子串了,只要计算i - p【i】,如果包括开头加了#后,应该是 i - p【i】 <= 1,则说明这个回文串是包含原串开头的。


奇妙之处:
回文串的总个数是O(n^2)的,我们用了O(n)的空间表示O(n^2)个东西






本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

91

主题

47

精华

1916

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1916

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-14-2014 01:56 PM | 显示全部楼层
昨天做了要做这道题,正好需要。
回复 支持 反对

使用道具 举报

 楼主| 发表于 12-14-2014 02:05 PM | 显示全部楼层
MengMa 发表于 12-14-2014 01:56 PM
昨天做了要做这道题,正好需要。

很早就想写了。。。一直没写 太费功夫
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表