2472 - SUBSTRING
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 number 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 longest 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<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<map> #include<queue> using namespace std; int main() { int i,j,k,t,ans; char s[55]; int a[55][55]; cin>>t; while(t--) { cin>>s;ans=0; memset(a,0,sizeof(a)); int len=strlen(s); for(i=0; i<len; i++) { for(j=len-1; j>i ;j--) { int nn=i,mm=j; while(s[nn] == s[mm] && nn<len) { a[i][nn]=nn-i; if(a[i][nn]>ans) ans=a[i][nn]; nn++;mm--; } } } //cout<<ans<<endl; if(ans==0) cout<<s[0]<<endl; else { for(i=0; i<=len; i++) for(j=0; j<=len; j++) { if(a[i][j]==ans) { //cout<<i<<"**"<<j<<endl; for(int k=i; k<=j; k++) { cout<<s[k];} goto end; } } end: cout<<endl; } } return 0; }