I'll try anything once

人生苦短,何妨一试

字符串的操作 --- 最长回文子串

前言

最近在看编程之法,发现真是一本好书,特别的好,已经把需要整理的相关数结对应的常用问题全部整理了一遍,然后自己只需要按照整理的去收撸一遍就可以了.终于在15号之前把字符串部分看完了.然后发现Manacher算法很有灵魂,很漂亮,而且自己也看了有两天才明白,其实如果静下心去看的话,1个小时是可以解决的,自己太浮躁了.

最长回文子串

这是个老生畅谈的问题了,自己之前刷leetcode的时候就遇到了,然后很多地方都会有这个问题,自己之前也懒,没有去整理,遇到一次,记一次….
对于这个问题,在编程之法上,共总结了两种方法
1.中心拓展法
枚举所有子串,逐一判断各个子串是否为回文串,如果是回文串,则记录并更新最长回文串的长度,这总方法过于残暴,虽然实现起来很简单.
考虑到回文字符串的特征,其是关于中间位置对称的,所以可以使用中间拓展方式,譬如:aba,其是以b为中心向两边拓展,并且相同.所以只需要进行遍历中心位置即可,然后动态的更改最长子串的长度.

在回文字符串需要考虑是偶数还是奇数,譬如abc和abbc.所以做了奇数和偶数的判断,可以看到上述算法的复杂度为O(n*3)因为预先不知到为奇数还是偶数,所以默认就都执行一遍.那么有没有一个在线性时间内就可以得出结果的算法呢,答案是有的,就是下述的Manacher算法(马拉车算法), emmmm 不得不吐槽这个翻译.

2.Manacher算法

Manacher’s算法是Manacher在1975年提出的一个在线性时间里找出给定字符串中全部回文子串的算法,随着人们的研究,人们发现Manacher’s算法也可以用来求给定字符串的 最长 回文子串,当然也是线性时间。

实现
其实其原理很简单.
1. 数据的预处理
考虑到回文字符串的长度是分为奇偶的,为了方便处理,需要预先进行处理,Manacher算法在输入字符串的每个字符之间加了一个特殊的字符,其可以是# 等,为了就是将字符串的长度全部转化为奇数(关于为啥每个字符串之间加了一个特殊的字符就是奇数了,举个例子,若是字符串的长度为n, 那么需要插入的特殊符号的个数为n+1个,n+n+1也就铁定是奇数了),同时为了简化处理过程中遍历字符串对边界条件的判断,在开头和结尾再添加两个另一种特殊字符,该特殊字符要保证不会出现在任何输入字符串里
《字符串的操作 --- 最长回文子串》

  1. 从s[1]开始遍历s, 同时需要记住如下两点:
    • 回文串: 已经进行预处理之后,我们只需要考虑回文串为奇数的情况,同时回文串的特性就是对称,这一点很重要
    • 考虑s中的任一回文子串,该回文串的中心字符在s中的索引记为center,这个回文串中某个字符在s中的索引是i,那么该字符在该回文串中对称字符的索引 j = 2 * center – i ,见下图:
      《字符串的操作 --- 最长回文子串》
      求出其对称点的原因是,在正常情况下,P[i]的值是等于P[j]的,可以自行验证,下面会具体讨论出现的各种情况,以及P[i]如何赋值.
  2. 代码实现
    我们的目的就是通过遍历s[i]来填充我们的辅助数组P[i], P[i]代表以s[i]为中心的回文字符串向左右扩展的长度.之后,选取P[]中数值最大的及为最长的回文子串的长度,若是要返回该最长的子串,只需要求出该最大回文串在原s中的开始位置即可(start = (center-P[center])/2),关于原因,可自行举例然后计算.
    需要的变量如下:

    类型 变量 作用
    数组 P P[i]代表以s[i]为中心的回文字符串向左右扩展的长度
    int center 代表目前已知最长回文子串的中心位置
    int mx 代表目前已知最长回文子串的在s中的右边界 center+P[center]
    int i 当前遍历的位置,需要求出对应的P[i]
    int j i关于center的对称点

    在遍历时共有两种情况

    1. s[i]在目前一直最长回文子串内部.可知i一定在center的右边,因为是按顺序遍历s, center已知, i未知.
      1. i + P[j] < mx
        这种情况的意思就是:
        《字符串的操作 --- 最长回文子串》
        对于这种情况,就很明朗了, P[i]肯定是等于P[j]的,因为i关于center对称的点j,以j为中心的回文字符串是完全落在以center为中心的回文字符串里面的,然后按照对称性可知P[i] = P[j] = P[2*center – i]

      2. i + P[j] >= mx
        《字符串的操作 --- 最长回文子串》
        表示有一部分是落在了目前最长子回文串的外部,其至少是可以延伸到mx处的,大于mx的部分,无法根据对称性得出结果,但是我们目前可暂令P[i] = mx-i(其也是根据对称性得出的,若是对对称性有些疑惑,可自行举例分析.)
        由如上的结果可以得出 P[i] = min(P[2*center – i], mx-i)

    2. s[i]在目前已经超出了最长回文子串外部
      这种情况,在该循环内是无法得知的,所以只能暂时使P[i] = 0,之后,再拓展,然后更新P[];

reference

点赞

发表评论

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

5 + 15 =