回文，亦称回环，是正读反读都能一样的字符串。例如“12321”、“abba”等。 现在给你一个字符串，请你找出其中长度最长的回文。 输入描述: 输入有多组数据。每组数据有一行，包含一个长度小于100个字符的字符串s，且仅由字母和数字构成。如果有多个长度相等的回文，仅输出第一个。 输出描述: 对应每一组输入，输出其中长度最长的回文字符串。 输入例子: abcabccbaddaabcabccbaddabcc 输出例子: abccbaccbaddabcc
#include
#include
#include
#include
#include
#include
using namespace std;
string traslate(const string &str){
string ret;
ret.push_back('$');
ret.push_back('#');
for (unsigned int i = 0; i < str.length(); i++){
ret.push_back(str[i]);
ret.push_back('#');
}
return ret;
}
void recyle(const string &strx){
string stry = traslate(strx);
int maxid = 0, id = 0, ans = 0;
int *p = new int[stry.length()];
for (int i = 1; i < int(stry.length()-1); i++){
if (i < maxid)
p[i] = min(p[2 * id - i], maxid - i);
else
p[i] = 1;
while (stry[i + p[i]] == stry[i - p[i]])
p[i]++;
if (p[i] + i>maxid){
maxid = p[i] + i;
id = i;
}
if (p[i] > p[ans])
ans = i;
}
for (int i = ans - p[ans] + 1; i < ans + p[ans]; i++){
if (stry[i] != '#')
cout << stry[i];
}
cout << endl;
delete[] p;
}
int main(){
//ifstream in("input.txt");
//cin.rdbuf(in.rdbuf());
string str;
while (cin >> str){
recyle(str);
}
return 0;
}
