【PAT甲级】Longest Symmetric String

喜欢ctrl的cxk

发布于 2019-11-08 14:36:03

3040

发布于 2019-11-08 14:36:03

文章被收录于专栏：Don的成长史

                 本文链接：[https://blog.csdn.net/weixin\_42449444/article/details/89459876](https://blog.csdn.net/weixin_42449444/article/details/89459876)

Problem Description：

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:

解题思路：

这道题在天梯赛出现过：【GPLT】L2-008 最长对称子串。用ans来记录最长对称子串的长度，然后从后往前找第一个相同的字符，找到后就用t2往前、t1往后来寻找对称子串，直到字符不相等或者t1、t2相遇为止。

AC代码：

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

int main()
{
    string str;
    getline(cin,str);
    int len = str.length();
    int ans = 1;   //用来记录最长对称子串的长度
    for(int i = 0; i < len-1; i++)
    {
        for(int j = len-1; j >= i; j--)
        {
            if(str[i] == str[j])  //从后往前找第一个相同的字符
            {
                int t1 = i, t2 = j;
                bool flag = true;    //用来记录是不是对称字符串
                while(t1 <= t2)   //判断是不是对称字符串,t1往后,t2往前,直到t1,t2相遇为止
                {
                    t1++;
                    t2--;
                    if(str[t1] != str[t2])  //若不是对称字符串
                    {
                        flag = false;
                        break;
                    }
                }
                if(flag)
                {
                    ans = max(ans,j-i+1);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/04/22 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度