最长回文子串(C/C++)

最长回文子串(C/C++)最长回文子串(C/C++)

大家好,又见面了,我是你们的朋友全栈君。

给定一个字符串,求它的最长回文子串的长度。

思路:从给定字符串的头部开始,在每个字符的位置处设置两个指针,分别向前和向后两个方向依次判断各字符是否相等,当两个指针指向的字符不相等时计算回文子串的长度。重复这样的过程,直至扫描到字符串的最后一个字符为止。

内层的两个 for 循环,它们分别对于以 i 为中心的,长度为奇数和偶数的两种情况,整个代码遍历中心位置 i 并以之扩展,找出最长的回文。

注意:回文子串长度的计算方法

代码如下:

//最长回文子串
#include <iostream>

using namespace std;

//*s为字符串,n为字符串的长度
int LagPalindrome(char *str, int n)
{
	int count = 0;
	int max = 0;//最长回文子串的长度
	if (str == NULL || n<1)
	{
		return 0;
	}
	for (int i = 0; i < n; i++)
	{		
		//子串为奇数时
		for (int j = 0; (i-j)>=0&&(i+j)<n; j++)
		{
			if (str[i - j] != str[i + j])
			{
				break;
			}
			count = 2 * j + 1;
		}
		if (count > max)
		{
			max = count;
		}
		//子串为偶数时
		for (int k = 0; (i - k)>=0 && (i + k + 1) < n; k++)
		{
			if (str[i - k] != str[i + k+1])
			{
				break;
			}
			count=2*k + 2;
		}
		if (count > max)
		{
			max =count ;
		}
	}
	
	return max;
}

int main( )
{
	char str[] = "abccba";
	int n = strlen(str);
	int MaxLen;
	MaxLen = LagPalindrome(str, n);
	
	cout << "最长回文子串的长度是:"<<MaxLen<<endl;

	return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/141985.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 光纤交换机划ZONE

    光纤交换机划ZONE虽然我们在媒体上可以看到许多厂商声称有SAN交换机可以选择,其实这是一种假象,绝大多数厂商的SAN交换机都是OEM几个主要品牌的。目前在SAN交换机方面真正有实力主要有:IBM、Brocade(博科)、Cisco、McDATA等,像EMC这样的软件厂商基本上都是OEM其它厂商的SAN交换机产品。下图为Brocade(博科)交换机,本文也以其为例,记录其划分命令和划分方法:连接交换机…

  • BeanUtils工具类中的copyProperties方法使用「建议收藏」

    BeanUtils工具类中的copyProperties方法使用「建议收藏」文章目录1、两个包下的BeanUtils.copyProperties对比2、BeanUtils.copyProperties的深浅拷贝问题2.1、浅拷贝和深拷贝2.2、BeanUtils.copyProperties深浅拷贝问题1、两个包下的BeanUtils.copyProperties对比BeanUtils是开发中常用到的工具类,而获取这一工具类主要是通过导入org.springframework.beans.BeanUtils或者org.apache.commons.beanutils.Bean

  • linux时间戳转换为时间_linux时间转换为时间戳

    linux时间戳转换为时间_linux时间转换为时间戳/***************************************************************************************************************************************************************************************************uni…

  • 网页内容变化监控提醒

    网页内容变化监控提醒有很多的人都需要查看网站的变化并且提醒,比如说股票的股市,商品的价格等等。这次案例以实时监控天气温度来简要的说明监控方法,监控的时广州的实时气温,网站会不断的更新当前的气温。首先打开软件网页自动操作通用工具PageOperator,在任务菜单中新建一个刷新操作。点击添加按钮,并把网址输入到对应的地方。点击自动获取,获取网站的编码方案,点击添加,…

  • 如何搭建自己的SpringBoot源码调试环境? SpringBoot源码(一)「建议收藏」

    如何搭建自己的SpringBoot源码调试环境? SpringBoot源码(一)「建议收藏」1前言这是SpringBoot2.1源码分析专题的第一篇文章,主要讲如何来搭建我们的源码阅读调试环境。如果有经验的小伙伴们可以略过此篇文章。2环境安装要求IntelliJIDEAJDK1.8Maven3.5以上3从github上将SpringBoot源码项目下载下来首先提供SpringBoot2.1.0的github地址:点这里下载因为要进行阅读源码和分析源码项目,我们是不是要在里面写一些注释帮助我们阅读理解源码,因此需要将SpringBoot源码项目fork到自己的github

  • python语言关键字是_Python 关键字

    python语言关键字是_Python 关键字1Python关键字概述Python关键字(或称保留字)指的是Python语言中一些已经被赋予特定意义的单词。也属于是标识符,但是不能被用作普通标识符。以下标识符被作为Python语言的保留字或称关键字,共35个。关键字的拼写必须与这里列出的完全一致。FalseawaitelseimportpassNonebreak…

    2022年10月24日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号