文档章节

O(n) 求 最长回文子串

吟啸_徐行
 吟啸_徐行
发布于 2013/07/10 11:55
字数 1088
阅读 233
收藏 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
leetcode——最长回文子串

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

wikison
2015/08/20
0
0
lintcode最长回文子串(Manacher算法)

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

余二五
2017/11/16
0
0
manacher算法求最长回文串

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

iaccepted
2015/09/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周三乱弹 —— 有一天考拉麻麻拉肚子了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @瘟神灬念 :分享周汇洋的单曲《Man Srae(曼斯拉之舞)》:美滋滋。。。。 手机党少年们想听歌,请使劲儿戳(这里) 我听了一下 赶紧关了, ...

小小编辑
40分钟前
12
3
oh-my-zsh 自定义

GitHub 地址 基于 oh-my-zsh 的自定义配置,增加了一些个人常用插件与皮肤。 采用的是 git submodule 来维护,包括 oh-my-zsh,之所以这么搞,主要是手头有多台 linux 需要维护, 每台机器、...

郁也风
今天
6
0
Docker安装踩坑:E_FAIL 0x80004005的解决

参考 菜鸟教程--Windows Docker 安装 http://www.runoob.com/docker/windows-docker-install.html 官方文档-Install Docker Toolbox on Windows https://docs.docker.com/toolbox/toolbox_in......

karma123
今天
6
0
js垃圾回收机制和引起内存泄漏的操作

JS的垃圾回收机制了解吗? Js具有自动垃圾回收机制。垃圾收集器会按照固定的时间间隔周期性的执行。 JS中最常见的垃圾回收方式是标记清除。 工作原理:是当变量进入环境时,将这个变量标记为“...

Jack088
昨天
18
0
大数据教程(10.1)倒排索引建立

前面博主介绍了sql中join功能的大数据实现,本节将继续为小伙伴们分享倒排索引的建立。 一、需求 在很多项目中,我们需要对我们的文档建立索引(如:论坛帖子);我们需要记录某个词在各个文...

em_aaron
昨天
27
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部