大家好,又见面了,我是你们的朋友全栈君。
给定一个字符串,求它的最长回文子串的长度。
思路:从给定字符串的头部开始,在每个字符的位置处设置两个指针,分别向前和向后两个方向依次判断各字符是否相等,当两个指针指向的字符不相等时计算回文子串的长度。重复这样的过程,直至扫描到字符串的最后一个字符为止。
内层的两个 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账号...