t0ur1st

题目描述：

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

输入描述：

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

输出描述：

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

输入样例：

Is PAT&TAP symmetric?

输出样例：

11

解题思路：

我一开始的思路就是暴力破解，用ans来记录最长对称子串的长度，然后通过无脑遍历翻转所有子串来寻找对称子串，不断更新ans最后输出。提交代码之后直接TLE…25分得了17分。嗯，然后我换了个思路，从后往前找第一个相同的字符，找到后就用t2往前、t1往后来寻找对称子串，直到字符不相等或者t1、t2相遇为止。

AC代码：TLE代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    getline(cin,str);
    int len = str.length();
    int ans = -1e5;   //用来记录最长对称子串的长度
    for(int i = 0; i < len; i++)
    {
        string s1 = "";
        for(int j = i; j < len; j++)
        {
            s1 = str.substr(i,j);
            string s2 = s1;
            reverse(s2.begin(),s2.end());  //将字符串翻转
            if(s1 == s2)   //若字符串对称
            {
                int temp = s1.length();
                ans = max(ans,temp);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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--;
                    if(str[t1] != str[t2])   //若不是对称字符串
                    {
                        flag = false;
                        break;
                    }
                }
                if(flag)
                {
                    ans = max(ans,j-i+1);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}