首页 > 其他分享 >最长回文长度

最长回文长度

时间:2024-10-26 09:47:54浏览次数:6  
标签:字符 暴力 算法 parr 长度 扩充 最长 回文

  小伙伴们大家好,今天给大家带来一道算法题:如何找一个字符串中的最大回文长度。何为回文?简单来讲就是正着读和倒着读结果相同,如aba。

暴力算法

  给定一个字符串s=“abac”,经典的暴力算法思想是对每个字符进行回文串扩充。i=0,对a进行扩充,发现其左边没有元素,因此回文长度为0。i=1时,对b进行扩充,发现其左右元素均为a,再对两边a进行扩充,但扩充均失败,因此i=1时回文长度为3。同理i=2,i=3。

  并且这种方法存在一个弊端,比如字符串等于122131221。虽然我们能找到最大回文为122131221,但是1221这个回文串却被我们忽视了,它无法找到偶数长度回文串。这是因为偶数长度回文其中心轴为虚轴。

  那该如何进行改进呢?答案是为每个字符前后添加字符#,上述字符串变#1#2#2#1#3#1#2#2#1,这样再对每个字符进行扩充时无论回文长度为奇数还是偶数都可以找出了(扩充时包含#)。比如回文1221就包含在第二个#的扩充回文串里:1#2#2#1。

  那我们添加的字符必须为#吗?必须为特殊字符吗?答案是否定的。其实是任意的,你可以在每个字符前后均添加1,2......为什么呢?因此我们添加了字符后,每次进行扩充比较时,均为原字符比原子符,扩充字符比扩充字符。扩充字符对原子符的扩充没有障碍,因此随意(但要保持相等,你不能一个补充1一个补充2这种)。

Manacher算法

算法分析

  Manacher算法是对上述暴力扩充的一种优化。其将扩充情况分为两大类,第二大类又分为三个小类。不过在此之前,我们需要认识下述几个概念。

  R:扩充回文长度的右边界,初始时为-1。比如12321(其实还有添加的额外字符这里方便观看省略),i=0时回文串范围为0~0,R=0>-1,更新为0。i=1时,回文串范围为1~1>0,更新为1。i=2时,扩充回文串为12321,范围为0~4>1,更新R为4。i=3时,回文范围为3~3<4,不更新。i=4时,R=4~4=4,不更新。

  C:当R改变时,C也进行改变,初始时为-1。C为此R下的回文串中心。如i=2时,R变为4发生更新,则C更新为2。

  回文半径:如i=2时,回文串为12321,则回文半径为3。(123)

第一类:当前位置落在R之外

  很简单,直接暴力扩,无优化。如123,初始时R=-1,i=0时发现其落在R之外,直接暴力扩,更改R=0。i=1时落在R之外,继续暴力扩。

第二类:当前位置落在R里

  存在下图关系: 

  在此基础上继续分类:

1>i‘位置回文序列在L-R内部

如下图:

 

  这种情况,我们无需对i位置进行求解,只需一步即可,完成对暴力算法的优化。

2>i’位置回文序列在L-R之外

如下图:

 

  这种情况,我们也可以直接得到i位置回文情况,完成对暴力算法的优化。 

3>i‘回文落在L-R边界

代码展示

#include<iostream>
using namespace std;
string manacherstring(string s){
	string str="";
	for(int i=0;i<s.length();i++){
		if(i==0){
			str.push_back('#');
		}   
		str.push_back(s[i]);
		str.push_back('#');
	}
	return str;
}
int maxlength(string s){
	int R=-1,C=-1;//R-1为回文右边界 
	int parr[s.length()];
	for(int i=0;i<s.length();i++){
		//至少不用验证的区域先赋值给parr数组 
		parr[i]=R>i?min(parr[2*C-i],R-i):1;
		//看看能否继续扩充(公共部分虽然有些情况无需扩充) 
		while(i+parr[i]<s.length()&&i-parr[i]>=0){
			if(s[i+parr[i]]==s[i-parr[i]]){
				parr[i]++;
			}
			else{
				break;
			}
		}
		if(i+parr[i]>R){
			R=i+parr[i];
			C=i;
		}
	}
	int max=-1;
	for(int i=0;i<s.length();i++){
		if(max<parr[i]){
			max=parr[i];
		}
	}
	return max-1;
}
int main(){
	string s="123513421";
	s=manacherstring(s);
    int length=maxlength(s);
    cout<<length;
} 

  for循环第一句解释:

 

返回max-1:大家可以自己举个例子(因为原串中含有#,并且parr为半径)。

  分享到此结束,感谢大家支持!! 

  

标签:字符,暴力,算法,parr,长度,扩充,最长,回文
From: https://blog.csdn.net/weixin_74901355/article/details/143224824

相关文章

  • 最长的Y题解
    考虑将Y单独拎出来,用数组存储他的下标,那么将第\(x\)个Y转移至第\(y\)个Y就需要\(a[x]-b[y]-1\)次操作。发现一个问题:第一次从左移动至\(y\)需要减1,第二次从左移动需要减2……如图:这似乎是一个很麻烦的问题,我们的某知名\(lyh\)教授是通过指针(应该是吧)解决的。......
  • <Project-11 Calculator> 计算器 0.5 液体、长度、温度单位 转换器 liquid_measures HTM
    前言这是一个综合性的单位换算工具,提供了多种常用计量单位之间的转换功能。不断完善style各页面风格统一,格式一致。容量单位换算支持在公制单位(升、毫升、立方厘米)美制容量单位(加仑、夸脱、品脱、杯、液体盎司)厨房计量单位(汤匙、茶匙、米杯)之间相互转换长度单位换算公......
  • pbootcms网站栏目url字数长度限制的修改方法
    要修改PBootCMS网站栏目URL的最大长度,您可以通过数据库管理工具来调整相关表中的字段长度。以下是详细的步骤:1.备份数据库在进行任何数据库修改之前,强烈建议先备份数据库,以防止意外数据丢失。2.使用数据库管理工具您可以使用如phpMyAdmin、Navicat、DBeaver等数据库管......
  • 【每日一题】LeetCode - 最长回文子串
    在字符串相关的算法题中,寻找最长回文子串是一个经典且富有挑战性的题目。本篇将详细分析并推导两种有效的解决方案:动态规划法和中心扩展法。题目描述给定一个字符串s,我们需要找到s中最长的回文子串。回文是指正着读和反着读都相同的字符串。例如,输入"babad"时,输出可......
  • 2024-10-23:最高频率的 ID。用go语言,给定两个长度相等的整数数组 nums 和 freq, 其中num
    2024-10-23:最高频率的ID。用go语言,给定两个长度相等的整数数组nums和freq,其中nums中的每个元素表示一个ID,而freq中的每个元素表示对应ID在此次操作后出现的次数变化。如果freq[i]为正数,则表示在这次操作中nums[i]的ID会增加freq[i]次;如果freq[i]为负数,则表示在这次操作中nums[i......
  • 代码随想录算法训练营day22和day23 | 77. 组合 216.组合总和III 17.电话号码的字母
    学习资料:https://programmercarl.com/回溯算法理论基础.html回溯法backtracking:for循环控制递归数量,暴力搜索:组合、切割、子集、排列、棋盘今天学了组合和切割可以画个N叉树的图来帮助理解回溯过程组合又包括1.单个数组(要加startIndex参数)或多个数组;2.数组内有无重复元素;3.数......
  • 01.期货比的不是谁赚的最多,而是比谁活得最长
    在经历股票十年的摸爬滚打以及持续亏损下,深刻意识到股票不是给人炒的,是给国家和企业融资的,个人根本不适合参与,现在都把a股市场叫做缅a,十年人生亏损10多万,遗憾离场。​ 转战期货,开通后转入5万元,当时是年后3-4月份,持有4月鸡蛋多单5手,被连着打亏损200多点,亏损7000多遗憾离场。​ 第......
  • 栈实现回文
    栈实现回文分数15作者liudan单位石家庄铁道大学输入一个字符串,判断该字符串是否为回文。回文就是字符串中心对称,从左向右读和从右向左读的内容是一样的。(不含空格)输入格式:先输入字符串的长度,不超过100个字符长度,回车,然后依次输入字符,以回车结束字符串输入。输出格式:......
  • 八重回文划分法:最多/最少 回文/非回文 子序列/子串 划分
    只考虑常数字符集,所以关于字符集的复杂度都没算进来。最少非回文子串划分答案是\(1\)或\(2\)或者无解,参考CF1951E的题解。时间复杂度:\(\mathcalO(n)\)。最少非回文子序列划分考虑最少非回文子串划分的情况,可以发现答案是\(2\)的情况也不可能划分成\(1\)个子序列,所......
  • 128. 最长连续序列(中)
    目录题目法一、桶排思想---备忘录法二、Set题目给定一个未排序的整数数组nums,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。示例1:输入:nums=[100,4,200,1,3,2]输出:4解释:最长数字连续序列是[1,2......