文档章节

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

pathenon
 pathenon
发布于 2012/06/24 14:05
字数 1288
阅读 3894
收藏 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应该是已经找出的最靠右的回文子串的中间位置吧~~
【DSAA】Longest Palindromic Substring

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

jiantao88
01/04
0
0
lintcode最长回文子串(Manacher算法)

题目来自lintcode, 链接:http://www.lintcode.com/zh-cn/problem/longest-palindromic-substring/ v最长回文子串 给出一个字符串(假设长度最长为1000),求出它的最长回文子串,你可以假定...

余二五
2017/11/16
0
0
leetcode——最长回文子串

关于这道题,我的第一想法是针对回文串的特性,对字符串的每个字符(奇数回文串)或者每两个字符(偶数回文串)向两边开始扩展分析。在这个过程中不断发现最新的最长回文串。显然这个算法的复...

wikison
2015/08/20
0
0
Manacher's Algorithm 马拉车算法

这个马拉车算法Manacher‘s Algorithm是用来查找一个字符串的最长回文子串的线性方法,由一个叫Manacher的人在1975年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性,这是非常了...

机器的心脏
2017/12/02
0
0
最长回文子串与Manacher算法

题目描述 给定一个字符串,求它的最长回文子串的长度。 最简单粗暴的方法就是,枚举全部的字符串,然后每个都判断一下是不是回文,然后得到长度最长的字符串。显然,这个方法是可行的,可是也...

yejq8
2015/05/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

基于redis的分布式锁

redisson提供了基于redis的分布式锁实现方式,本文就尝试了下锁的使用方式。Redisson同时还为分布式锁提供了异步执行的相关方法,第二节执行介绍。 一、可重入锁验证 同一个jvm里面同一线程的...

noob_chr
16分钟前
3
0
CPU性能过剩提升乏力影响未来行业发展吗?

虽然CPU仍然在不断发展,但是它的性能已经不再仅仅受限于单个处理器类型或制造工艺上了。和过去相比,CPU性能提升的步伐明显放缓了,接下来怎么办,成为横亘在整个行业面前的大问题。 自201...

linux-tao
18分钟前
1
0
设计模式“6”大原则!

面向对象设计原则 概述 对于面向对象软件系统的设计而言,在支持可维护性的同时,提高系统的可复用性是一个至关重要的问题,如何同时提高一个软件系统的可维护性和可复用性是面向对象设计需要...

Java干货分享
35分钟前
7
0
mybatis学习(1)

JDBC连接方式: 1.底层没有使用连接池,操作数据库需要频繁的创建和关闭连接,消耗资源。 2.写原生的JDBC代码在JAVA中,一旦需要修改SQL的话(比如表增加字段),JAVA需要整体重新编译,不利...

杨健-YJ
今天
5
0
怎么组织文档

可以从以下几个方面考虑组织文档: ☐ 各种分支的界面截图和对应的类及文件 ☐ 框架或类图 ☐ 流程图 ☐ 时序图 ☐ 注意事项

-___-
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部