Substring，

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

答案：

#include<iostream>

#include<string>

#include<algorithm>

using namespace std;

int main()

{

 

int n;

cin>>n;

while(n--){

string s,r;

cin>>s;

int maxlen=0;

for(int i=0;i!=s.size();i++){

for(int j=s.size()-i;j>0&&j>maxlen;j--){

string s2=s;

reverse(s2.begin(),s2.end());

if(s2.find(s.substr(i,j))!=string::npos)r=s.substr(i,j),maxlen=j;

}

}

cout<<r<<endl;

}

}