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

题意

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

思路

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

1. 1.先求子串长度为奇数的情况，长度为 r-l-1 。
2. 2.再求子串长度为偶数的情况，长度同样为 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;
}