Manacher解决最长回文子串

2024-06-07 15:48

本文主要是介绍Manacher解决最长回文子串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题描述

给定一个字符串,求解该字符串的最长回文子串

解法一

以字符串中的每个字符为中心,枚举其最长的回文子串,注意奇数和偶数长度的子串

int longPalindrome(char*str)
{int len = strlen(str);int maxlen = 1;for(int i = 0; i < len-1; i++){int j;for(j = 1; i - j >= 0 && i + j < len; j ++)if(str[i - j] != str[i + j])break;maxlen = maxlen > (j - 1) * 2 + 1 ? maxlen : (j - 1) * 2 + 1;for(j = 0; i - j >= 0 && i + j + 1 < len; j++)if(str[i-j] != str[i+j+1])break;maxlen = maxlen > 2 * j ? maxlen : 2 * j;}return maxlen;
}

Manacher

该算法为DP算法,我们可以保存上面中心扩展的结果来计算后面的点,如下图

这里写图片描述
我们用f[i]表示以i为中心的最长的回文子串长度
如果我们从左到右得到位于center的结果f[center]了,那么现在计算以i为中心的f[i]
其中rb为以center为中心的最大右边界,left是i以center为对称的点
1. 当i + j < rb时,我们根据对称性,我们可以直接得到 f[ i ] = f[ left ]
2. 当i + j >= rb时,我们直接从rb位置开始扩展以i为中心的回文子串,同解法一方法一样扩展到最长位置

对于奇数和偶数的情况,我们在每两个字符之间插入一个特殊字符来进行处理,就可以统一奇数和偶数的处理了

如abababa变为#a#b#a#b#a#b#a#,在我们下面的算法中,直接用f[i]表示扩展时的j值,对于以i为中心的原始最长回文子串长度即为f[i]

int manacher(char*str)
{int len = strlen(str);int maxlen = 1;char helpstr[2 * len + 2];for(int i = 0; i <= len; i++){helpstr[2 * i] = '#';helpstr[2 * i + 1] = str[i];}int helplen = strlen(helpstr);int f[helplen];int center = 1;int rb = 2;f[0] = 0;f[1] = 1;for(int i = 2; i < helplen; i ++){if(i > rb)f[i] = 0;elsef[i] = (i + f[2 * center - i]) < rb ? f[2 * center - i] : center + f[center] - i;while(helpstr[i-f[i]-1] == helpstr[i+f[i]+1] && (i+f[i]+1) > rb && (i-f[i]-1) >= 0)f[i] ++;if(i + f[i] > rb){rb = i + f[i];center = i;}maxlen = maxlen > f[i] ? maxlen : f[i];}return maxlen;
}

这篇关于Manacher解决最长回文子串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1039607

相关文章

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

如何解决线上平台抽佣高 线下门店客流少的痛点!

目前,许多传统零售店铺正遭遇客源下降的难题。尽管广告推广能带来一定的客流,但其费用昂贵。鉴于此,众多零售商纷纷选择加入像美团、饿了么和抖音这样的大型在线平台,但这些平台的高佣金率导致了利润的大幅缩水。在这样的市场环境下,商家之间的合作网络逐渐成为一种有效的解决方案,通过资源和客户基础的共享,实现共同的利益增长。 以最近在上海兴起的一个跨行业合作平台为例,该平台融合了环保消费积分系统,在短

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

【VUE】跨域问题的概念,以及解决方法。

目录 1.跨域概念 2.解决方法 2.1 配置网络请求代理 2.2 使用@CrossOrigin 注解 2.3 通过配置文件实现跨域 2.4 添加 CorsWebFilter 来解决跨域问题 1.跨域概念 跨域问题是由于浏览器实施了同源策略,该策略要求请求的域名、协议和端口必须与提供资源的服务相同。如果不相同,则需要服务器显式地允许这种跨域请求。一般在springbo

hihocoder1050 : 树中的最长路

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到,小Ho得到了一棵二叉树玩具,这个玩具是由小球和木棍连接起来的,而在拆拼它的过程中,小Ho发现他不仅仅可以拼凑成一棵二叉树!还可以拼凑成一棵多叉树——好吧,其实就是更为平常的树而已。 但是不管怎么说,小Ho喜爱的玩具又升级换代了,于是他更加爱不释手(其实说起来小球和木棍有什么好玩的是吧= =)。小Ho手

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ