最长对称子串

PTA L2-008 最长对称子串

题目描述

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。

输入格式：
输入在一行中给出长度不超过1000的非空字符串。

输出格式：
在一行中输出最长对称子串的长度。

输入样例：
Is PAT&TAP symmetric?
输出样例：
11

题意分析

第一眼看到这道题是没有什么思路的，但是回头发现很多人a了这题，我又仔细的思考了很久，想到一种方法，让字符串与翻转之后的它进行比较，如果出现相等的就继续比较，同时对ans加一直到下一个不相同的出现为止。再将ans与最大值比较存储后归零。但是TLE了。不过有好的pta也是给了我21分（总分25。回来之后又想了想，查了一下资料，发现一种更好用的方法。参考文章：CSDN——职业炮灰
具体思路就是遍历字符串的每一个字符，每次循环中都对这个字符两边的字符进行判断，出现不一样的就退出内层循环。
这里面分有两种情况，一种是最长回文串的长度是奇数，一种是偶数。其实大体上是一样的。具体可以看代码

代码实现

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    getline(cin,s);
    int l=s.size(),len=0;
    for(int i=0;i<l;i++)
    {
        for(int j=0;i-j>=0&&i+j<l;j++)
        {
            if(s[i-j]!=s[i+j])
                break;
            len=2*j+1>len?2*j+1:len;
        }
        for(int j=0;i-j>=0&&i+j<l;j++)
        {
            if(s[i-j]!=s[i+j+1])
                break;
            len=(2*j+2)>len?(2*j+2):len;
        }
    }
    cout<<len<<endl;
    return 0;
}

总结以及向对自己说的话

昨晚的天体训练赛垫底了。。。好多基础算法也都还不会，不能再沉迷于水题了，要学习。学习。学习！