文档章节

O(n) 求 最长回文子串

吟啸_徐行
 吟啸_徐行
发布于 2013/07/10 11:55
字数 1088
阅读 231
收藏 0

    首先:大家都知道什么叫回文串吧,这个算法要解决的就是一个字符串中最长的回文子串有多长。这个算法可以在O(n)的时间复杂度内既线性时间复杂度的情况下,求出以每个字符为中心的最长回文有多长,

    这个算法有一个很巧妙的地方,它把奇数的回文串和偶数的回文串统一起来考虑了。这一点一直是在做回文串问题中时比较烦的地方。这个算法还有一个很好的地方就是充分利用了字符匹配的特殊性,避免了大量不必要的重复匹配。
    算法大致过程是这样。先在每两个相邻字符中间插入一个分隔符,当然这个分隔符要在原串中没有出现过。一般可以用‘#’分隔。这样就非常巧妙的将奇数长度回文串与偶数长度回文串统一起来考虑了(见下面的一个例子,回文串长度全为奇数了),然后用一个辅助数组P记录以每个字符为中心的最长回文串的信息。P[id]记录的是以字符str[id]为中心的最长回文串,当以str[id]为第一个字符,这个最长回文串向右延伸了P[id]个字符。
    原串:    w aa bwsw f d 
    新串:    # w # a # a # b # w # s # w # f # d #
辅助数组P: 1 2 1 2 3 2 1 2 1 2 1 4 1 2 1 2 1 2 1
    这里有一个很好的性质,P[id]-1就是该回文子串在原串中的长度(包括‘#’)。如果这里不是特别清楚,可以自己拿出纸来画一画,自己体会体会。当然这里可能每个人写法不尽相同,不过我想大致思路应该是一样的吧。
    好,我们继续。现在的关键问题就在于怎么在O(n)时间复杂度内求出P数组了。只要把这个P数组求出来,最长回文子串就可以直接扫一遍得出来了。
    由于这个算法是线性从前往后扫的。那么当我们准备求P[i]的时候,i以前的P[j]我们是已经得到了的。我们用mx记在i之前的回文串中,延伸至最右端的位置。同时用id这个变量记下取得这个最优mx时的id值。(注:为了防止字符比较的时候越界,我在这个加了‘#’的字符串之前还加了另一个特殊字符‘$’,故我的新串下标是从1开始的)
好,到这里,我们可以先贴一份代码了。

 

void pk()
{ 
   int i; int mx = 0; int id; 
   for(i=1; i<n; i++)
   { 
      if( mx > i ) p[i] = MIN( p[2*id-i], mx-i ); 
      else p[i] = 1; 
      for(; str[i+p[i]] == str[i-p[i]]; p[i]++); 
      if( p[i] + i > mx )
      {
            mx = p[i] + i;
            id = i;
      }
    }
}



    代码是不是很短啊,而且相当好写。很方便吧,还记得我上面说的这个算法避免了很多不必要的重复匹配吧。这是什么意思呢,其实这就是一句代码。


if( mx > i )
    p[i] = MIN( p[2*id-i], mx-i );


就是当前面比较的最远长度mx>i的时候,P[i]有一个最小值。这个算法的核心思想就在这里,为什么P数组满足这样一个性质呢?
   (下面的部分为图片形式)


此主题相关图片如下:8_56_4f13d6e009ae79e.png (88KB)

两个基本题:hdu 3068  poj 3974

#
include < cstdio > #include < cstring > const int M = 110010 * 2;
char str[M]; //start from index 1 int p[M]; char s[M]; int n; void checkmax(int &ans,int b){ if(b>ans) ans=b;
}
inline int min(int a, int b) {
	return a < b ? a : b;
}
void kp() {
	int i;
	int mx = 0;
	int id;
	for(i = 1; i < n; i++) {
		if(mx > i)
			p[i] = min(p[2 * id - i], p[id] + id - i);
		else p[i] = 1;
		for(; str[i + p[i]] == str[i - p[i]]; p[i]++);
		if(p[i] + i > mx) {
			mx = p[i] + i;
			id = i;
		}
	}
}
void pre() {
	int i, j, k;
	n = strlen(s);
	str[0] = '$';
	str[1] = '#';
	for(i = 0; i < n; i++) {
		str[i * 2 + 2] = s[i];
		str[i * 2 + 3] = '#';
	}
	n = n * 2 + 2;
	str[n] = 0;
}
void pt() {
	int i;
	int ans = 0;
	for(i = 0; i < n; i++)
		checkmax(ans, p[i]);
	printf("%d\n", ans - 1);
}
int main() {
	int T, _ = 0;
	while(scanf("%s", s) != EOF) {
		pre();
		kp();
		pt();
	}
	return 0;
}



本文转载自:http://www.cnblogs.com/wuyiqi/archive/2012/06/25/2561063.html

共有 人打赏支持
吟啸_徐行
粉丝 18
博文 109
码字总数 15832
作品 0
深圳
高级程序员
加载中

评论(1)

liupengs
liupengs
赞一个
【XSY2715】回文串 树链剖分 回文自动机

题目描述   有一个字符串 ,长度为 。有 个操作:   求    题解   毒瘤题。   先把所有操作保存下来,求出最终的字符串。   观察到操作过程中每个字符串都只会出现一次,而且左边...

ez_yww
01/11
0
0
Manacher's Algorithm 马拉车算法

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

机器的心脏
2017/12/02
0
0
manacher算法求最长回文串

求最长回文串可以使用manacher算法来达到O(n)时间内得出结果,之所以降到O(n)是因为减少了很多重复匹配。 思路如下: 1.把所有字符串都变成奇数个字母的串,方法很简单,就是在所有字母前后加...

iaccepted
2015/09/10
0
0
史上最清晰--O(n)时间求字符串的最长回文子串解读

真的很烦有些人,想写博客么,又不好好写,最起码自己好好看一遍,纠纠错,写写感悟,只顾自己看懂而不加以探讨,那你写博客还有什么意义呢?更何况,看不看的懂还两说,接下来就为大家解释一...

牧师-Panda
2016/09/17
21
0
manacher&&后缀数组

一、manacher: 1、主体思想: 用一个辅助数组P记录以每个字符为中心的最长回文半径。 P[i]最小为1, 此时回文串为Str[i] 本身。 MaxId:之前所有求出的回文串所能到达的最右端点 id:能到达...

luodanyu_
2017/12/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

你为什么在Redis里读到了本应过期的数据

一个事故的故事 晚上睡的正香突然被电话吵醒,对面是开发焦急的声音:我们的程序在访问redis的时候读到了本应过期的key导致整个业务逻辑出了问题,需要马上解决。 看到这里你可能会想:这是不...

IT--小哥
今天
2
0
祝大家节日快乐,阖家幸福! centos GnuTLS 漏洞

yum update -y gnutls 修复了GnuTLS 漏洞。更新到最新 gnutls.x86_64 0:2.12.23-22.el6 版本

yizhichao
昨天
5
0
Scrapy 1.5.0之选择器

构造选择器 Scrapy选择器是通过文本(Text)或 TextResponse 对象构造的 Selector 类的实例。 它根据输入类型自动选择最佳的解析规则(XML vs HTML): >>> from scrapy.selector import Sele...

Eappo_Geng
昨天
4
0
Windows下Git多账号配置,同一电脑多个ssh-key的管理

Windows下Git多账号配置,同一电脑多个ssh-key的管理   这一篇文章是对上一篇文章《Git-TortoiseGit完整配置流程》的拓展,所以需要对上一篇文章有所了解,当然直接往下看也可以,其中也有...

morpheusWB
昨天
5
0
中秋快乐!!!

HiBlock
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部