首页 > 代码库 > PAT L2-008. 最长对称子串

PAT L2-008. 最长对称子串

题目链接:PAT L2-008. 最长对称子串

题意:

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

题解:

直接枚举中点,暴力一下

技术分享
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 
 5 const int N=2007;
 6 
 7 char a[N];
 8 
 9 int main()
10 {
11     gets(a);
12     int len=strlen(a),ans=0;
13     F(i,0,len-1)//奇数
14     {
15         int l=i,r=i;
16         while(l>0&&r<len-1&&a[l-1]==a[r+1])l--,r++;
17         ans=max(ans,r-l+1);
18     }
19     F(i,0,len-1)//偶数
20     {
21         int l=i,r=i+1;
22         if(a[l]!=a[r])continue;
23         while(l>0&&r<len-1&&a[l-1]==a[r+1])l--,r++;
24         ans=max(ans,r-l+1);
25     }
26     printf("%d\n",ans);
27     return 0;
28 }
View Code

 

PAT L2-008. 最长对称子串