L2-008 最长对称子串 (25 分)
对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?
,最长对称子串为s PAT&TAP s
,于是你应该输出11。
输入在一行中给出长度不超过1000的非空字符串。
在一行中输出最长对称子串的长度。
Is PAT&TAP symmetric?
11
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;
char s[1005];
int main()
{
cin.getline(s,1005); // 暴力找
int len = strlen(s);
int Max = 1, l,r,sum;
for(int i = 0; i < len; i ++)
{
l = i - 1;
r = i + 1;
sum = 1;
while(l >= 0 && r < len) // 从中间向两边扩散
{
if(s[l] == s[r]) l --, r++, sum += 2;
else break;
}
Max = max(sum,Max);
l = i;
r = i + 1;
sum = 0;
while(l >= 0 && r < len )
{
if(s[l] == s[r])l --, r ++, sum += 2;
else break;
}
Max = max(sum,Max);
}
printf("%d\n",Max);
return 0;
}