文档章节

字符串系列之最长回文子串

pathenon
 pathenon
发布于 2012/06/24 14:05
字数 1288
阅读 3.9K
收藏 1

问题描述:

    给定一个字符串S=A1A2...An,要求找出其最长回文子串(Longest Palindromic Substring)。所谓回文子串就是S的某个子串Ai...Aj为回文。例如,对字符串S=abcdcbeba,它的回文子串有:bcdcb,cdc,beb,满足题目要求的最长回文子串为bcdcb。

推理思路:

1.由于回文可能由奇数个字符组成,也可能由偶数个字符组成。对奇数回文的处理比较直观,只需要以某个字符为中心,依次向两边扩展即可。因此,我们可以通过如下方式把对偶数回文的处理转换成对奇数回文的处理:在字符边界添加特殊符号。例如,对字符串aba,预处理后变成#a#b#a#;对字符串abba,预处理后变成#a#b#b#a。可以看出,不管是奇数回文,还是偶数回文,在与处理后都变成奇数回文。在找出与预处理后字符串的最长回文后,只需要去除所有的#即为源字符串的最长回文。

2.对寻找字符串某类子串的问题,最简单直观的想法就是穷举出所有子串一一进行判别。这里也不例外,当然时间复杂度也很高,为O(n^3)。

3.对该问题,我们可以进行一定程度的简化处理。既然回文是一种特殊的字符串,我们可以以源字符串的每个字符为中心,依次寻找出最长回文子串P0, P1,...,Pn。这些最长回文子串中的最长串Pi = max(P1, P2,...,Pn)即为所求。请看源码:

string find_lps_native(const string &str)
{
    int center = 0, max_len = 0;
    for(int i = 1; i < str.length()-1; ++i)
    {
        int j = 1;

        //以str[i]为中心,依次向两边扩展,寻找最长回文Pi
        while(i+j < str.length() && i-j >= 0 && str[i+j] == str[i-j])
            ++j;
        --j;
        if(j > 1 && j > max_len)
        {
            center = i;
            max_len = j;
        }
    }

    return str.substr(center-max_len, (max_len << 1) + 1);
}

4.可以看出,上面做法的复杂度为O(n^2)。相比穷举字符串的做法,已经降低了一个量级的复杂度。但是仔细想想,上面的算法还有改进空间吗?当然有!而且改进后能够把复杂度降低到O(n)!这就是大名鼎鼎的 Manacher’s Algorithm。请看下文分析:

    举例说明:对字符串S=abcdcba而言,最长回文子串是以d为中心,半径为3的子串。当我们采用上面的做法分别求出以S[1]=a, S[2]=b, S[3]=c, S[4]=d为中心的最长回文子串后,对S[5]=c,S[6]=b...还需要一一进行扩展求吗?答案是NO。因为我们已经找到以d为中心,半径为3的回文了,S[5]与S[3],S[6]与S[2]...,以S[4]为对称中心。因此,在以S[5],S[6]为中心扩展找回文串时,可以利用已经找到的S[3],S[2]的相关信息直接进行一定步长的偏移,这样就减少了比较的次数(回想一下KMP中next数组的思想)。优化的思想找到了,我们先看代码:

string find_lps_advance(const string &str)
{
    //find radius of all characters
    vector<int> p(str.length(), 0);
    int idx = 1, max = 0;
    for(int i = 1; i < str.length()-1; ++i)
    {
        if(max > i)
        {
            p[i] = p[(idx << 1) - i] < (max - i) ? p[(idx << 1) - i]:(max - i);
        }
        while(str[i+p[i]+1] == str[i-p[i]-1])
            p[i] += 1;
        if(i + p[i] > max)
        {
            idx = i;
            max = i+p[i];
        }
    }

    // find the character which has max radius
    int center = 0, radius = 0;
    for(int i = 0; i < p.size(); ++i)
    {
        if(p[i] > radius)
        {
            center = i;
            radius = p[i];
        }
    }

    return str.substr(center-radius, (radius << 1) + 1);
}

    这里进行简单的解释:上述代码中有三个主要变量,它们代表的意义分别是:

     p:以S[i]为中心的最长回文串的半径为p[i]。

     idx:已经找出的能够右延伸最远距离的回文子串的起始位置。

     max:已经找出的能够右延伸最远距离的回文子串的结束位置。

     算法的主要思想是:先找出所有的p[i],最大的p[i]即为所求。在求p[j] (j>i)时,利用已经求出的p[i]减少比较次数。

     代码中比较关键的一句是:

 p[i] = p[(idx << 1) - i] < (max - i) ? p[(idx << 1) - i]:(max - i);

    在求p[i]时,如果max>i,则表明已经求出的最长回文中包含了p[i],那么与p[i]关于idx对称的p[ (idx << 1) - i]的最长回文子串可以提供一定的信息。看了两幅图大概就明白什么意思了:

    求二者的最小值是因为当前能够获取的信息都来自max的左侧,需要进一步比较,求出以S[i]为中心的最长回文串。

5.除了上述的几种做法外,还可以利用动态规划以及后缀树来进行求解。下次进行介绍。

    结束行文之前,补充一句,对于字符串类的问题,建议多画一画,寻找其中的规律。

 

参考文献:1.http://www.akalin.cx/longest-palindrome-linear-time

 

© 著作权归作者所有

pathenon
粉丝 13
博文 21
码字总数 22328
作品 0
海淀
程序员
私信 提问
加载中

评论(1)

void-man
void-man
idx:已经找出的最长回文子串的起始位置。

idx应该是已经找出的最靠右的回文子串的中间位置吧~~
马拉车算法(Manacher's Algorithm)

这是悦乐书的第343次更新,第367篇原创 Manacher's Algorithm,中文名叫马拉车算法,是一位名叫Manacher的人在1975年提出的一种算法,解决的问题是求最长回文子串,神奇之处在于将算法的时间...

小川94
2019/06/04
0
0
马拉车算法(Manacher's Algorithm)

这是悦乐书的第343次更新,第367篇原创 Manacher's Algorithm,中文名叫马拉车算法,是一位名叫Manacher的人在1975年提出的一种算法,解决的问题是求最长回文子串,神奇之处在于将算法的时间...

osc_3jn62rhp
2019/06/04
2
0
leetcode 求一个字符串的最长回文子串

最长回文子串问题:给定一个字符串,求它的最长回文子串长度。如果一个字符串正着读和反着读是一样的,那它就是回文串。 给定一个字符串,求它最长的回文子串长度,例如输入字符串'35534321...

osc_my2aqmiz
2019/03/29
1
0
【DSAA】Longest Palindromic Substring

最近刷LeetCode遇到一个比较有意思的题目(Longest Palindromic Substring),求一个字符串的最大回文子串。题目本身并不难,但需要理清思路才好理解,借此文记录下。 题目 Given a string s...

jiantao88
2018/01/04
0
0
最长回文子序列/最长回文子串(DP,马拉车)

字符子串和字符子序列的区别 字符字串指的是字符串中连续的n个字符;如palindrome中,pa,alind,drome等都属于它的字串 而字符子序列指的是字符串中不一定连续但先后顺序一致的n个字符;如p...

osc_qdpqaoww
2019/07/20
2
0

没有更多内容

加载失败,请刷新页面

加载更多

小师妹学JavaIO之:文件写入那些事

简介 小师妹又对F师兄提了一大堆奇奇怪怪的需求,要格式化输出,要特定的编码输出,要自己定位输出,什么?还要阅后即焚?大家看F师兄怎么一一接招吧。 字符输出和字节输出 小师妹:F师兄,上...

flydean
16分钟前
12
1
直接显示StackOverflow的答题日期, 增加评论区回复的时间显示 ,修改时间显示到小时分。

// ==UserScript==// @name 直接显示StackOverflow的答题日期, 增加评论区回复的时间显示 ,修改时间显示到小时分。// @namespace http://tampermonkey.net/// @version ...

FalconChen
今天
36
0
Shader笔记_005 纹理

纹理最初的目的就是使用一张图片来控制模型的外观,通过纹理映射技术 我们可以把一张图粘贴在物体表面,逐纹素的控制模型的颜色。 通常美术建模的时候也会在软件里利用纹理展开技术把纹理展开成...

STONE-CITY
今天
12
0
iOS MVVM 与RAC结合使用

MVVM配合 RAC 更能发挥的淋漓尽致。 我们把 MVVM 第一篇的例子 KVO 的事件 替换成 配合RAC 框架使用, OC的话直接导入 : pod 'ReactiveObjC' Swift 直接用 RXSwift就可以。 把 ViewModel里加...

T型人才追梦者
今天
22
1
OSChina 周一乱弹 —— 影响心情的三座大山

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @薛定谔的兄弟 :分享洛神有语创建的歌单「我喜欢的音乐」: 《浮生(inst.)》- 忘乡 / 墨凡悦 手机党少年们想听歌,请使劲儿戳(这里) @凝小紫...

小小编辑
今天
102
2

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部