leetcode最长回文子串_最长回文子串算法

leetcode最长回文子串_最长回文子串算法C++实现——最长回文子串

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

作者:翟天保Steven
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处

题目描述:

给定一个仅包含小写字母的字符串,求它的最长回文子串的长度。

所谓回文串,指左右对称的字符串。

所谓子串,指一个字符串删掉其部分前缀和后缀(也可以不删)的字符串

(注意:记得加上while处理多个测试用例)

输入描述:

输入一个仅包含小写字母的字符串

输出描述:

返回最长回文子串的长度

示例:

输入:

cdabbacc

输出:

4

说明:

abba为最长的回文子串

解题思路:

这题用双循环解决。从头开始一层遍历,从后开始一层遍历;每个节点,令m=i,n=j,当某个位置str[m]与str[n]相等时进入while循环,m++、n–,同时用t记录回文一半长度的尺寸,若为回文则到中间位置,m会大于等于n;如果m和n相等,说明回文字符数为奇数,则回文长度为2*t+1,若m>n,说明回文字符数为偶数,则回文长度为2*t,同时更新max,max为最长回文长度。

测试代码:

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    string str;
    while(getline(cin,str))
    {
        int max=0;
        int size=str.size();
        for(int i=0;i<size;++i)
        {
            for(int j=str.size()-1;j>i;--j)
            {
                int m=i,n=j,t=0;
                while(str[m]==str[n])
                {
                    t++;
                    m++;
                    n--;
                    if(m>=n)
                    {
                        if(m==n)
                            t=2*t+1;
                        else
                            t=2*t;
                        if(t>max)
                            max=t;
                        break;
                    }
                }
            }
        }
        cout<<max<<endl;
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

发表回复

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

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