字符串--最长回文子串(暴力讲解+Manacher)

问题描述:给你一个字符串str,若子串s是回文串,则称s为str的回文子串,求s的最大长度

解法一:暴力匹配

对每一个字符,假定位置为i,匹配判断i+1与i-1位置是否相等,相等ans长度加一,否则停止。

              对奇数,ans=1;对偶数,ans初始为0.(不知道奇数偶数,两种都要写,最后取较大值)。奇数偶数都要判断,代码很长,复杂度O((2*N+1)*N)=O(N^2).

              比起一般暴力三方快一点。

解法二:Manacher

     严格复杂度O(N)       

     step1:预处理,将奇偶变为奇数。

             对于一个串str长度为n,有n-1个空格,首位有两个,对这些空处理,长度变成2n+1。

     可以加str中不存在的东西,比如#。

             step2: 构造数组p[n]

            数组p[i]来记录字符串s[i]最长回文串向左向右扩张p[i]长度的最大值。

     如图,对应的关系,p[i]-1正好是原字符串最长回文子串的长度。

如何求p[i]数组?

      求p[i]时,p[1]....p[n]是已知的。

      对任意位置i,可以扩张的范围是i±p[i],这个范围都是回文的。对于k+p[k](k=1,2,.....i-1)有最大值记为mx,有一个id(id的值就是前面mx取得最大值对应的p[k]的k的值),

     i关于id的位置是 j  (j=2*id-i),mx关于id对称点是my (my=2*id-mx).

     那么,从id两侧(从my到mx)一定是回文的。

 如果i+p[j]长度在mx之内就取它,如果i+p[j]长度不可控,在mx之外,就取mx-i

    总之取  p[i]=min(p[2*id-i],mx-i)

                  没有可利用的p[i]=1;接下来该怎样就怎样。

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
char s[10000],s2[100000];
int p[10000];
int size;
void Manacher(char *s,int * p)
{
	 size=strlen(s);
	p[0]=1;
	int id=0;
	int mx=1;
	for(int i=1;i<size;i++)
	{
		if(mx>i)
		{
			p[i]=min(p[2*id-i],mx-i);
		}
		else
		{
			p[i]=1;
		}
		for(;s[i+p[i]]==s[i-p[i]]&&(i-p[i]>=0);p[i]++);
		if(mx<i+p[i])
		{
			mx=i+p[i];
			id=i;
		}
	}
	
} 

int main()
{
	while(1)
	{
	scanf("%s",s2);
	size=strlen(s2);
	
	for(int i=0;i<2*size+1;i++)
	{
		s[i]='#';
		s[++i]=s2[i/2];
	}
printf("%s\n",s);
	Manacher(s,p);

for(int i=0;i<size;i++) 
	printf("%d%c",p[i]-1," \n"[i==size-1]); 
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python攻城狮

Python数据科学(七)- 资料清理(Ⅱ)1.资料转换2.处理时间格式资料3.重塑资料4.学习正则表达式5.实例处理

注意:这里的时间转换后的格式可以根据需要设定,eg:dt.strftime('%Y/%m/%d')

1163
来自专栏数据结构与算法

34:回文子串

34:回文子串 总时间限制: 1000ms 内存限制: 65536kB描述 给定一个字符串,输出所有长度至少为2的回文子串。 回文子串即从左往右输出和从右往...

3716
来自专栏Script Boy (CN-SIMO)

软件工程个人作业01

题目:      像二柱子那样,花二十分钟写一个能自动生成三十道小学四则运算题目的 “软件”,要求:除了整数以外,还要支持真分数的四则运算(需要验证结果的正确...

2190
来自专栏racaljk

Julia体验 语言基础

以前听说过Julia,不过那时候官网还处于时不时宕机状态,最近Julia发布了1.0 released版本到处都是它的资讯,官网良心自带简体中文,趁着热度我也来...

1792
来自专栏海天一树

程序员必须掌握的8大排序算法

分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序)...

3238
来自专栏小樱的经验随笔

洛谷 P1598 垂直柱状图【字符串+模拟】

P1598 垂直柱状图 题目描述 写一个程序从输入文件中去读取四行大写字母(全都是大写的,每行不超过72个字符),然后用柱状图输出每个字符在输入文件中出现的次数...

3115
来自专栏SeanCheney的专栏

《Pandas Cookbook》第01章 Pandas基础

公司网址,http://www.dunderdata.com(dunder是蒸馏朗姆酒的残留液体,取这个名字是类比数据分析过程) GitHub地址:https...

1472
来自专栏武培轩的专栏

京东2019春招Java工程师编程题题解

生成回文串 题目描述 对于一个字符串,从前开始读和从后开始读是一样的,我们就称这个字符串是回文串。 例如"ABCBA","AA","A"是回文串,而"ABCD"...

3078
来自专栏机器学习入门

挑战程序竞赛系列(86):3.6极限情况(3)

挑战程序竞赛系列(86):3.6极限情况(3) 传送门:AOJ 2201: Immortal Jewels 翻译参考至hankcs: http://www....

21910
来自专栏coder修行路

Go基础之--反射

反射:可以在运行时动态获取变量的相关信息 反射需要导入reflect 反射中重要函数的演示 反射有几下几个重要的函数: reflect.TypeOf :获取变量...

2708

扫码关注云+社区

领取腾讯云代金券