2521 - SubString
时间限制 : 1 秒
内存限制 : 128 MB
You are given a string input.You are to find the longest substring of input such that the reversal of the substring is also a
substring of input.In case of a tie,return the string that occurs earliest in input.
Note well:The substring and its reversal may overlap partially or completely.The entire original string is itself a valid
substring.The best we can do is find a one character substring,so we implement the tie-breaker rule of taking the earliest
one first.
题目输入
The first line of input gives a single integer,1<=N<=10,the num of test cases.
Then follow,for each test case,a line containing between 1 and 50 characters,inclusive.
Each character of input will be an uppercase letter('A'-'Z').
题目输出
Output for each test case the longer substring of input such that the reversal of the substring is also a substring of input.
输入/输出样例
输入格式
3 ABCABA XYZ XCVCX
输出格式
ABA X XCVCX
C语言解答
#include<stdio.h> #include<string.h> char str[101]; int pd(int s,int p) { int i,j,len,pd,len2; char a1[101],a2[101]; len=strlen(str); for(i=s;i<=s+p-1;i++) a1[i-s]=str[i]; a1[i-s]='\0'; for(i=0;i<=len-p;i++) { for(j=i;j<=i+p-1;j++) a2[j-i]=str[j]; a2[j-i]='\0'; len2=strlen(a2); pd=0; for(j=0;j<len2;j++) if(a2[len2-1-j]!=a1[j]) { pd=1; break; } if (pd==0) return 0; } return 1; } int main() { int j,k,len,p,s,y; scanf("%d",&k); while(k>=0) { gets(str); y=0; len=strlen(str); for(p=len;p>=1;p--) { for(s=0;s<=len-p;s++) if(pd(s,p)==0) { for(j=s;j<=s+p-1;j++) printf("%c",str[j]); printf("\n"); y=1; break; } if(y==1) break; } k--; } return 0; }
C++解答
#include<iostream> #include<cstring> using namespace std; int map[55][55]; int main() { int tcase,i,j,len,m; char str1[55],str2[55]; cin>>tcase; while(tcase--) { cin>>str1; len=strlen(str1); memset(map,0,sizeof(map)); for(i=0;i<len;i++) str2[i]=str1[len-i-1]; int maxlen=0; for(i=0;i<len;i++) for(j=0;j<len;j++) if(str1[i]==str2[j]) { map[i+1][j+1]=map[i][j]+1; if(maxlen<map[i+1][j+1]) { maxlen=map[i+1][j+1]; m=i+1; } } for(i=m-maxlen;i<m;i++) cout<<str1[i]; cout<<endl; } return 0; }