文档章节

O(n) 求 最长回文子串

吟啸_徐行
 吟啸_徐行
发布于 2013/07/10 11:55
字数 1088
阅读 219
收藏 0
点赞 0
评论 1

    首先:大家都知道什么叫回文串吧,这个算法要解决的就是一个字符串中最长的回文子串有多长。这个算法可以在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;
}



© 著作权归作者所有

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

评论(1)

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

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

ez_yww ⋅ 01/11 ⋅ 0

Manacher's Algorithm 马拉车算法

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

机器的心脏 ⋅ 2017/12/02 ⋅ 0

史上最清晰--O(n)时间求字符串的最长回文子串解读

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

牧师-Panda ⋅ 2016/09/17 ⋅ 0

manacher&&后缀数组

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

luodanyu_ ⋅ 2017/12/22 ⋅ 0

manacher算法求最长回文串

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

iaccepted ⋅ 2015/09/10 ⋅ 0

leetcode——最长回文子串

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

wikison ⋅ 2015/08/20 ⋅ 0

lintcode最长回文子串(Manacher算法)

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

余二五 ⋅ 2017/11/16 ⋅ 0

Manacher算法求解最长回文子串

一、背景 最近在LintCode上面刷题时遇到了一个求解最长回文子串的问题,这个题目可以使用暴力的方式去进行求解,但算法的时间复杂度至少就是O(n^2)级别了,后面看讨论区时发现了一个比较有意...

丶legend ⋅ 前天 ⋅ 0

[转载] Manacher 算法

转自: https://61mon.com/index.php/archives/181/ 原文作者: 刘毅 md文件获取: https://github.com/61mon/61mon.com-blog-articles 感谢原文作者。 一:背景 给定一个字符串,求出其最长...

u013553529 ⋅ 2017/11/25 ⋅ 0

【算法系列 四】 String

字符串循环左移(九度OJ1362),要求时间复杂度O(N),空间复杂度O(1) 这是一道基本的题目,简单说来就是三次翻转 比如:abcdef 左移两位 cdefab 过程: ab 翻转 ba cdef 翻转 fedc 将上面两个翻...

Hosee ⋅ 2016/04/18 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

BS与CS的联系与区别【简】

C/S是Client/Server的缩写。服务器通常采用高性能的PC、工作站或小型机,并采用大型数据库系统,如Oracle、Sybase、InFORMix或 SQL Server。客户端需要安装专用的客户端软件。 B/S是Brower/...

anlve ⋅ 50分钟前 ⋅ 0

发生了什么?Linus 又发怒了?

在一个 Linux 内核 4.18-rc1 的 Pull Request 中,开发者 Andy Shevchenko 表示其在对设备属性框架进行更新时,移除了 union 别名,这引发了 Linus 的暴怒。 这一次 Linus Torvalds 发怒的原...

问题终结者 ⋅ 今天 ⋅ 0

在树莓派上搭建一个maven仓库

在树莓派上搭建一个maven仓库 20180618 lambo init 项目说明 家里有台树莓派性能太慢。想搭建一个maven私服, 使用nexus或者 jfrog-artifactory 运行的够呛。怎么办呢,手写一个吧.所在这个...

林小宝 ⋅ 今天 ⋅ 0

Spring发展历程总结

转自与 https://www.cnblogs.com/RunForLove/p/4641672.html 目前很多公司的架构,从Struts2迁移到了SpringMVC。你有想过为什么不使用Servlet+JSP来构建Java web项目,而是采用SpringMVC呢?...

onedotdot ⋅ 今天 ⋅ 0

Python模块/包/库安装(6种方法)

Python模块/包/库安装(6种方法) 冰颖机器人 2016-11-29 21:33:26 一、方法1: 单文件模块 直接把文件拷贝到 $python_dir/Lib 二、方法2: 多文件模块,带setup.py 下载模块包(压缩文件zip...

cswangyx ⋅ 今天 ⋅ 0

零基础学习大数据人工智能,学习路线篇!系统规划大数据之路?

大数据处理技术怎么学习呢?首先我们要学习Python语言和Linux操作系统,这两个是学习大数据的基础,学习的顺序不分前后。 Python:Python 的排名从去年开始就借助人工智能持续上升,现在它已经...

董黎明 ⋅ 今天 ⋅ 0

openJdk和sun jdk的区别

使用过LINUX的人都应该知道,在大多数LINUX发行版本里,内置或者通过软件源安装JDK的话,都是安装的OpenJDK, 那么到底什么是OpenJDK,它与SUN JDK有什么关系和区别呢? 历史上的原因是,Ope...

jason_kiss ⋅ 今天 ⋅ 0

梳理

Redux 是 JavaScript 状态容器,提供可预测化的状态管理。 它是JS的状态容器,是一种解决问题的方式,所以即可以用于 react 也可以用于 vue。 需要理解其思想及实现方式。 应用中所有的 stat...

分秒 ⋅ 今天 ⋅ 0

Java 后台判断是否为ajax请求

/** * 是否是Ajax请求 * @param request * @return */public static boolean isAjax(ServletRequest request){return "XMLHttpRequest".equalsIgnoreCase(((HttpServletReques......

JavaSon712 ⋅ 今天 ⋅ 0

Redis 单线程 为何却需要事务处理并发问题

Redis是单线程处理,也就是命令会顺序执行。那么为什么会存在并发问题呢? 个人理解是,虽然redis是单线程,但是可以同时有多个客户端访问,每个客户端会有 一个线程。客户端访问之间存在竞争...

码代码的小司机 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部