【PAT甲级 - C++题解】1040 Longest Symmetric String

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

✍个人博客https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址PAT题解集合
📝原题地址题目详情 - 1040 Longest Symmetric String (pintia.cn)
🔑中文翻译最长回文子串
📣专栏定位为想考甲级PAT的小伙伴整理常考算法题解祝大家都能取得满分
❤️如果有收获的话欢迎点赞👍收藏📁您的支持就是我创作的最大动力💪

1040 Longest Symmetric String

Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given Is PAT&TAP symmetric?, the longest symmetric sub-string is s PAT&TAP s, hence you must output 11.

Input Specification:

Each input file contains one test case which gives a non-empty string of length no more than 1000.

Output Specification:

For each test case, simply print the maximum length in a line.

Sample Input:
Is PAT&TAP symmetric?
Sample Output:
11

题意

需要我们求出给定字符串中回文子串的最长长度。

思路

这道题直接枚举即可对字符串的每个字符都进行枚举

先求子串长度为奇数的情况长度为 r-l-1 。
再求子串长度为偶数的情况长度同样为 r-l-1 。

最后输出得到的最长回文子串长度即可。

代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    //输入字符串
    string s;
    getline(cin, s);

    //计算最长回文子串
    int res = 0;
    for (int i = 0; i < s.size(); i++)
    {
        //先枚举奇数结点的情况
        int l = i - 1, r = i + 1;
        while (l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;
        res = max(res, r - l - 1);

        //再枚举偶数结点的情况
        l = i, r = i + 1;
        while (l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;
        res = max(res, r - l - 1);
    }

    //输出答案
    cout << res << endl;

    return 0;
}