文档章节

最长回文子串

900928yao
 900928yao
发布于 2014/09/14 09:48
字数 274
阅读 6
收藏 0

definition:一个字符串中连续的一段就是这个字符串的子串,而回文串指的是12421这种从前往后读和从后往前读一模一样的字符串,所以最长回文子串的意思就是这个字符串中最长的身为回文串的子串

很容易想到枚举所有子串,这是很蠢的做法.

其实中中心开始往俩边找就行(O(N^2))

int LongestPalindrome(const char *s, int n)
{
	int i,j max,temp;
	if (0 == s || n < 1)
	{
		return 0 ;
	}

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; (i - j) >= 0 && (i + j) < n; ++j)
		{
			if (s[i - j] != s[i + j])break;
			temp = j*2 + 1;
		}
		
		if (temp > max )
		{
			max = temp;
		}

		for (int j = 0; (i-j) >= 0 && (i+j) <= n; ++j)
		{
			if(s[i-j] != s[i+j+1])break;
			temp = 2*j+2;
		}
		if (temp > max )
		{
			max = temp;
		}

		return max;


	}
}

    更加高效的做法是Manacher算法.

    

int p[1000], mx = 0, id = 0;memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) {
    p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
    while (s[i + p[i]] == s[i - p[i]]) 
        p[i]++;
    if (i + p[i] > mx) 
    {
        mx = i + p[i];
        id = i;
    }}


参考:https://github.com/julycoding/The-Art-Of-Programming-By-July


© 著作权归作者所有

共有 人打赏支持
900928yao
粉丝 0
博文 1
码字总数 274
作品 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
史上最清晰--O(n)时间求字符串的最长回文子串解读

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

牧师-Panda
2016/09/17
21
0
[leetcode] 5.最长回文子串

目录 [leetcode] 5.最长回文子串 回文 解法一:暴力求解法 解法二:改进的暴力求解法 解法三:马拉车算法 [leetcode] 5.最长回文子串 DATE: 2018-12-27 题目描述 给定一个字符串 ,找到 中最...

Cheehool
2018/12/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

容器服务

简介 容器服务提供高性能可伸缩的容器应用管理服务,支持用 Docker 和 Kubernetes 进行容器化应用的生命周期管理,提供多种应用发布方式和持续交付能力并支持微服务架构。 产品架构 容器服务...

狼王黄师傅
昨天
3
0
高性能应用缓存设计方案

为什么 不管是刻意或者偶尔看其他大神或者大师在讨论高性能架构时,自己都是认真的去看缓存是怎么用呢?认认真真的看完发现缓存这一块他们说的都是一个WebApp或者服务的缓存结构或者缓存实现...

呼呼南风
昨天
12
0
寻找一种易于理解的一致性算法(扩展版)

摘要 Raft 是一种为了管理复制日志的一致性算法。它提供了和 Paxos 算法相同的功能和性能,但是它的算法结构和 Paxos 不同,使得 Raft 算法更加容易理解并且更容易构建实际的系统。为了提升可...

Tiny熊
昨天
3
0
聊聊GarbageCollectionNotificationInfo

序 本文主要研究一下GarbageCollectionNotificationInfo CompositeData java.management/javax/management/openmbean/CompositeData.java public interface CompositeData { public Co......

go4it
昨天
3
0
阿里云ECS的1M带宽理解

本文就给大家科普下阿里云ECS的固定1M带宽的含义。 “下行带宽”和“上行带宽” 为了更好的理解,需要先给大家解释个词“下行带宽”和“上行带宽”: 下行带宽:粗略的解释就是下载数据的最大...

echojson
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部