Problem Statement | |||||||||||||
|
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. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
| - | The substring and its reversal may overlap partially or completely. | ||||||||||||
| - | The entire original string is itself a valid substring (see example 4). | ||||||||||||
Constraints | |||||||||||||
| - | input will contain between 1 and 50 characters, inclusive. | ||||||||||||
| - | Each character of input will be an uppercase letter ('A'-'Z'). | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||
| 4) | |||||||||||||
| |||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
//代码：
///////////////////////////////////////////////////////////////////////////////////////////////
#include
#include
using namespace std;
class ReverseSubstring
{
public:
string findReversed(string input)
{
string res,temp;
int len;
bool flag;
len = 0;
for(int i=0;i<(int)input.size();i++)
{
for(int j = 1;j<=(int)(input.size()-i);j++)
{
temp = input.substr(i,j);
flag = isPD(temp,input);
if(flag)
{
if(len<(int)temp.size())
{
res = temp;
len= res.size();
}
}
}
}
if(len == 0)
{
len = 1;
res = input.substr(0,1);
}
return res;
};
string resever(string a)
{
string b;
for(int i=0;i<(int)a.size();i++)
{
b.insert(0,1,a[i]);
}
return b;
};
bool isPD(string c,string in)
{
string t;
c = resever(c);
for(int i = 0;i<=(int)(in.size()-c.size());i++)
{
t = in.substr(i,c.size());
if(t == c)
{
return true;
}
}
return false;
};
};
int main()
{
string input,output;
ReverseSubstring revSubstr;
while(true)
{
cin>>input;
output = revSubstr.findReversed(input);
cout<
}
/*
XBCDEFYWFEDCBZ
XYZ
ABCABA
FDASJKUREKJFDFASIREYUFDHSAJYIREWQ
ABCDCBA
*/
评论