# 14057: 【原4057】回文字符串

### 题目描述

author: 程序设计思想与方法助教组张涵 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4057

## 输入输出描述

### 输入

• 输入第一行为只含字母的字符串，长度不超过10000字符。

### 输出

• 输出结果第一行为最长回文字符串的长度
• 输出结果第二行为最长的回文字符串

### 程序运行示例1

#### Sample Input 1

``````abcdef
``````

#### Sample Output 1

``````0
``````

### 程序运行示例2

#### Sample Input 2

``````abcba
``````

#### Sample Output 2

``````5
abcba
``````

### 程序运行示例3

#### Sample Input 3

``````aAabccbaABcdcBA
``````

#### Sample Output 3

``````8
AabccbaA
``````

## 注意

• 不要显示多余的提示信息，避免输出判定错误
• 输出结束后不要输出任何内容，包括空格和换行
• 注意判断输出信息是否符合要求。

## skyzh's solution

``````#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

vector <bool> rev[10000];

int main() {
char str[20000];
int max_len = 0, str_s = 0, str_e = 0;
cin >> str;
int len = strlen(str);
for (int i = 0; i < len; i++) {
rev[i].resize(10000);
rev[i][i] = true;
}
for (int i = 0; i < len - 1; i++) {
if (str[i] == str[i + 1]) {
rev[i][i + 1] = rev[i + 1][i] = true;
max_len = 1;
}
}
for (int i = 1; i < len; i++) {
for (int j = 0; j < i - 1; j++) {
if (str[i] == str[j]) {
if (rev[j + 1][i - 1]) {
rev[j][i] = rev[i][j] = true;
max_len = max(max_len, i - j);
}
}
}
}
if (max_len == 0) {
cout << 0;
return 0;
}
cout << max_len + 1 << endl;
for (int i = 0; i < len; i++) {
if (rev[i][i + max_len]) {
str[i + max_len + 1] = 0;
cout << str + i;
return 0;
}
}
return 0;
}
``````

## victrid's solution

``````#include <iostream>
#include <cstring>

#define ODD 1
#define EVEN 0

using namespace std;

string input;
int length = 0;
int Leftrecorder = 0, Rightrecorder = 0;

int update(int i, int pattern)
{
int leftlimit, rightlimit;
if (pattern == ODD)
{
leftlimit = i;
rightlimit = i;
}
else
{
if (i + 1 >= length || input[i] != input[i + 1])
return 0;
leftlimit = i;
rightlimit = i + 1;
}

while (leftlimit - 1 >= 0 && rightlimit + 1 <= length - 1 && input[leftlimit - 1] == input[rightlimit + 1])
{
--leftlimit;
++rightlimit;
}
if (rightlimit - leftlimit > 0 && rightlimit - leftlimit > Rightrecorder - Leftrecorder)
{
Leftrecorder = leftlimit;
Rightrecorder = rightlimit;
}
}

int main()
{
cin >> input;
length = input.length();
for (int i = 0; i < length; ++i)
{
update(i, ODD);
update(i, EVEN);
}
if (Rightrecorder - Leftrecorder)
{
cout << Rightrecorder - Leftrecorder + 1 << endl;
for (int i = Leftrecorder; i <= Rightrecorder; ++i)
cout << input[i];
}
else
cout << 0;
return 0;
}
``````