【GPLT】L2-008 最长对称子串
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/88807953
题目描述：
对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-03-25 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录