算法:最长回文长度
发布日期:2022-02-02 02:58:02 浏览次数:6 分类:技术文章

本文共 2458 字,大约阅读时间需要 8 分钟。

问题描述

     给定一个字符串,求它的最长回文子串的长度(连续长度或者不连续长度)。

     回文串就是正着读和反着读都一样的字符串。

问题一:判断是否是回文

分析:根据定义进行判断,首尾不一致,则就不是回文

bool isPalinDrome(string& str, int begin, int end){// 判断是否是回文	int bg = begin, ed = end;	while (bg <= ed){		if (str[bg] == str[ed]){			bg++;			ed--;		}		else{			return false;		}	}	return true;}

问题二:连续条件下最长回文长度

分析:给定一个字符串,求它的最长连续的回文子串的长度,这里介绍两种方法;

最长回文串(可不连续)的意思是以某个字符为轴,分别往左右遍历的公共子串的最大长度(可不连续),那么不如将最大回文串改为一个字符串的顺序与逆序的最大公共子串(可不连续)。

方法1:暴力法(BruteForce,BF)

先求出该字符串的每一个子串,然后再分别判断每个子串是否是回文串,找到长度最长的那个。其中求出每个子串的时间复杂度为O(n2),判断是否为回文串的复杂度为O(n),两者是相乘关系,所以整个算法的时间复杂度为O(n3)。

int lengthBF(string& str){// 用暴力法进行求解	int len = str.size();	if (len == 0) return 0;	if (len == 1) return 1;	int longest = 1;	for (int i = 0; i < len; i++){		for (int j = i + 1; j < len; j++){			if (isPalinDrome(str, i, j)){				longest = longest>j - i + 1 ? longest : j - i + 1;			}		}	}	return longest;}

方法2:动态规划

对于字符串str,假设dp[i,j]=1表示子串str[i...j]是回文子串,那个必定存在dp[i+1,j-1]=1。这样最长回文子串就能分解成一系列子问题,可以利用动态规划求解了。动态规划的时间复杂度也为O(n2)。

      首先构造状态转移方程

      上面的状态转移方程表示,当str[i]=str[j]时,如果str[i+1...j-1]是回文串,则str[i...j]也是回文串;如果str[i+1...j-1]不是回文串,则str[i...j]不是回文串。

      初始状态

  • dp[i][i]=1
  • dp[i][i+1]=1 if str[i]==str[i+1]

      上式表示的意义是单个字符,两个相同字符都是回文串。

int lengthDP(string& str){// 用动态规划法进行求解	int len = str.size();	if (len == 0) return 0;	if (len == 1) return 1;	int longest = 1;	vector
> dp(len, vector
(len, 0));\ for (int t = 0; t < len; t++){ dp[t][t] = 1; if (str[t] == str[t + 1]) dp[t][t + 1] = 1; } for (int i = 0; i < len; i++){ for (int j = i + 1; j < len; j++){ if (str[i] == str[j]) dp[i][j] = dp[i + 1][j - 1]; else dp[i][j] = 0; if (dp[i][j] == 1) longest = longest>j - i + 1 ? longest : j - i + 1; } } return longest;}

问题三:不连续条件下字长回文长度

分析:定义dp_{i,j} 表示区间[i,j] 中最长回文串的长度(回文串的端点不一定是区间的端点),那么状态转移方程如下:

int LongestPalinDrome(string& str){	// dp[i][j] 表示区间[i,j]之中的最长回文长度	int len = str.size();	if (len == 0) return 0;	if (len == 1) return 1;	int longest = 1;	vector
> dp(len, vector
(len, 0)); for (int t = 0; t < len-1; t++){ dp[t][t] = 1; } int tmp1 = 0, tmp2 = 0; for (int lgt = 2; lgt <= len; lgt++){ // lgt表示子区间长度 for (int j = 0; j + lgt - 1 < len; j++){ // j表示子区间首序号 if (str[j] == str[j + lgt - 1]){ dp[j][j + lgt - 1] = dp[j + 1][j + lgt - 1 - 1] + 2;// dp[i][j] } tmp2 = std::max(dp[j + 1][j + lgt - 1], dp[j][j + lgt - 1 - 1]); dp[j][j + lgt - 1] = max(dp[j][j + lgt - 1], tmp2); } } return dp[0][len - 1];}

参考博文:

 

转载地址:https://blog.csdn.net/u010368556/article/details/89187285 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:C/C++---友元
下一篇:C/C++---随机数生成

发表评论

最新留言

不错!
[***.144.177.141]2024年03月08日 06时10分19秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java 符号 t_java – 运算符”不能应用于’T’,’T’表示有界泛型类型 2019-04-21
用matlab写出信源熵,计算离散信源的熵matlab实现 2019-04-21
php表单yii2,Yii2创建表单(ActiveForm)方法详解 2019-04-21
php 程序授权机制,授权认证详细说明 2019-04-21
java 命令提示符,如何使用Java打开命令提示符并插入命令? 2019-04-21
IP/tzgm.php,LianjiaSpider/在售数量.ipynb at master · BerSerK/LianjiaSpider · GitHub 2019-04-21
linux移动文件的脚本,使用Linux脚本移动文件 2019-04-21
linux查看系统所有变量,Linux系统各指标命令 2019-04-21
linux打印机守护程序,linux下怎么编写守护程序呢? 2019-04-21
嵌入式linux 设置时间,time_clock控件应用,使用命令date -s 12:00:00手动设置时间后,时间就停住不走了,我在Ubuntu和嵌入式Linux平台都测试到了... 2019-04-21
linux 8086下编译,Ubuntu18.04/Linux下安装DosBox进行8086汇编 2019-04-21
linux监控windows,zabbix监控之linux及windows客户端安装配置 2019-04-21
linux中怎么卸载tree,Liunx系统命令中tree命令详解 2019-04-21
linux 网络音箱 混音6,Linux音频编程(三)混音器介绍 2019-04-21
node与mysql开源_node与mysql的相互使用————node+mysql 2019-04-21
python合并列表重新排序_python – 将两个已排序的列表合并为一个更大的排序列表... 2019-04-21
vbs用mysql语句查询数据库_vbs脚本实现window环境下的mysql数据库的备份及删除早期备份... 2019-04-21
mysql连接nginx_nginx四层负载均衡连接mysql 2019-04-21
mysql截取栏目字符_substring从指定字符串开始截取(图) 2019-04-21
python 函数参数前面两个星号_Python中参数前面一个星号两个星号(*参数,**参数)起什么作用呢?... 2019-04-21