文档章节

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

pathenon
 pathenon
发布于 2012/06/24 14:05
字数 1288
阅读 3888
收藏 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

没有更多内容

加载失败,请刷新页面

加载更多

WinDbg

参考来自:http://www.cnit.net.cn/?id=225 SRV*C:\Symbols*http://msdl.microsoft.com/download/symbols ctrl + d to open dump_file Microsoft (R) Windows Debugger Version 6.12.0002.633......

xueyuse0012
今天
2
0
OSChina 周五乱弹 —— 想不想把92年的萝莉退货

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @罗马的王:分享松澤由美的单曲《地球ぎ》 很久没看圣斗士星矢了 《地球ぎ》- 松澤由美 手机党少年们想听歌,请使劲儿戳(这里) @开源中国首...

小小编辑
今天
12
1
springBoot条件配置

本篇介绍下,如何通过springboot的条件配置,控制Bean的创建 介绍下开发环境 JDK版本1.8 springboot版本是1.5.2 开发工具为 intellij idea(2018.2) 开发环境为 15款MacBook Pro 前言 很多时候,...

贺小五
今天
1
0
javascript source map 的使用

之前发现VS.NET会为压缩的js文添加一个与文件名同名的.map文件,一直没有搞懂他是用来做什么的,直接删除掉运行时浏览器又会报错,后来google了一直才真正搞懂了这个小小的map文件背后的巨大...

粒子数反转
昨天
1
0
谈谈如何学Linux和它在如今社会的影响

昨天,还在农耕脑力社会,今天已经人工智能技术、大数据、信息技术的科技社会了,高速开展并迅速浸透到当今科技社会的各个方面,Linux日益成为人们信息时代的到来,更加考验我们对信息的处理程...

linux-tao
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部