最长回文子串(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)


相关推荐

  • Linux下性能监控工具介绍

    Linux下性能监控工具介绍

  • 【WLAN】【基础知识】WIFI那些事儿之PMF

    【WLAN】【基础知识】WIFI那些事儿之PMFTaggedparameters->Tag:RSNInformation->RSNCapabilities:从assocreq中发现相关标志位没有使能,说明STA没有使能PMFRSNCapabilities:%0000000000000000[74-75]xx…………..Reserved……..0…….Managemen

  • StrictMode总结「建议收藏」

    StrictMode总结「建议收藏」Android2.3提供一个称为严苛模式(StrictMode)的调试特性,Google称该特性已经使数百个Android上的Google应用程序受益。首先先整体介绍:StrictMode.setThreadPolicy(newStrictMode.ThreadPolicy.Builder()//线程策略(ThreadPolicy).det

  • jquery和vue冲突吗_jquery和vue的区别

    jquery和vue冲突吗_jquery和vue的区别问题:一个h5项目同时引用了vue.js和jquery.js,发现jquery绑定的事件失效。原因是:vue会重新渲染dom,加上是异步实例vue.所以正常写程序的话jq的$()获取的元素不是vue渲染后的元素.解决办法:先加载vue.js,让页面渲染完成后加载jq,给jq绑定ready事件$(document).ready(function(){…

  • left join on 和where条件的放置[通俗易懂]

    left join on 和where条件的放置[通俗易懂]select*fromtdleftjoin(selectcase_idassup_case_id,count(*)supervise_numberfromtd_kcdc_case_sup_infogroupbycase_id)suponsup.sup_case_id=td.case_idwhere

  • ADB安装卸载应用[通俗易懂]

    ADB安装卸载应用[通俗易懂]一、目的使用adb快速安装apk手机app使用adb卸载app(卸载手机自带应用,root下)二、操作2.1adb安装apk手机USB连接电脑(连接成功进入adb)执行adbinstall-r<apk绝对路径>只需要将文件拉近cmd窗口中便会自动解析路径(最好将apk放到c盘)手机中确认安装即可…

发表回复

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

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