Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given “Is PAT&TAP symmetric?”, the longest symmetric sub-string is “s PAT&TAP s”, hence you must output 11.
Input Specification:
Each input file contains one test case which gives a non-empty string of length no more than 1000.
Output Specification:
For each test case, simply PRint the maximum length in a line.
Sample Input: Is PAT&TAP symmetric? Sample Output: 11
方法1：动态规划法#include<cstdio>#include<cstring>const int maxn=1010;char a[maxn];int dp[maxn][maxn];//dp[i][j]等于1表示i到j是回文，等于0表示i到j不是回文int main(){ gets(a); memset(dp,0,sizeof(dp)); int len=strlen(a),ans=1; for(int i=0;i<len;i++){ dp[i][i]=1; if(i<len-1&&a[i]==a[i+1]){ dp[i][i+1]=1; ans=2; } } for(int L=3;L<=len;L++){ for(int i=0;i+L-1<len;i++){ int j=i+L-1; if(a[i]==a[j]&&dp[i+1][j-1]==1){ dp[i][j]=1; ans=L; } } } printf("%d/n",ans); return 0;}方法2：暴力法，最后一个测试点错误，不知错哪里#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=1010;char a[maxn];int main(){ gets(a); int len=strlen(a),ans=1; for(int i=0;i<len;i++){ int j,l=i,r; for(j=len-1;j>i;j--){ if(a[j]==a[i]){ r=j; break; } } if(j>i){ while(l<r){ if(a[l]!=a[r]) break; l++,r--; } if(l>=r){ ans=max(ans,j-i+1); } } } printf("%d/n",ans); return 0;}新闻热点
疑难解答
