14057: 【原4057】回文字符串

题目

题目描述

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

问题描述

回文字符串是具有回文特性的字符串：即该字符串从左向右读和从右向左读都一样，单独的字母不作为回文字符串，例如abcddcba即为一个长度为8的回文字符串。 编写一个程序，输入一个全是字母的字符串，找出字符串中最长的回文字符串，输出最长回文字符串的长度和最长的回文字符串（长度相同的输出第一个），若无回文字符串，只输出0。

输入输出描述

输入

• 输入第一行为只含字母的字符串，长度不超过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;
}