Codeup_22562：问题 A: 【字符串】最长回文子串

Problem Description

输入一个字符串，求出其中最长的回文子串。子串的含义是：在原串中连续出现的字符串片段。回文的含义是：正着看和倒着看相同。如abba和yyxyy。在判断回文时，应该忽略所有标点符号和空格，且忽略大小写，但输出应保持原样（在回文串的首部和尾部不要输出多余字符）。输入字符串长度不超过5000，且占据单独的一行。应该输出最长的回文串，如果有多个，输出起始位置最靠左的。

Input

一行字符串，字符串长度不超过5000。

Output

字符串中的最长回文子串。

Sample Input

Confuciuss say:Madam,I'm Adam.

Sample Output

Madam,I'm Adam

提示

首先解决“判断时忽略标点，输出进却要按原样”的问题？ 可以用一个简单的方法：
预处理。构造一个新字符串，不包含原来的标点符号，而且所有字符变成大写（顺便解决了大小写的问题）。
用到的函数：	
（1）isalpha(c)用来检查c是否为字母，如果是字母，则返回1；否则返回0。	
（2）isdigit(c)用来检查c是否为数字（0～9），如果是数字，则返回1；否则返回0。	
（3）toupper(c)用来将c字符转换为大写字母，返回c对应的大写字母。	
（4）tolower(c)用来将c字符转换为小写字母，返回c对应的小写字母。

原题链接

• Codeup_22562：问题 A: 【字符串】最长回文子串

解题思路

• 对原字符串进行处理，将处理后的字符放入结构体数组中，并记录他们在原字符串中的位置。
• 动态规划求dp的过程中，每当有最大回文子串的长度更新，记录首尾元素的原位置。
• dp求解完成后，记录的首尾元素的原位置构成区间[low, high]，即为最大回文子串在原字符串中的位置。

代码实现（C++）

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

#define MaxSize 5005

typedef struct handledChar {
    char data;      // 字符数据
    int index;      // 在原字符串中的索引
} node;

bool dp[MaxSize][MaxSize];
char s[MaxSize];
int size, len, low, high, maxLen;
vector<node> handleS;

void handle() {
    handleS.clear();
    size = strlen(s);
    for (int i = 0; i < size; i++) {
        if (isalpha(s[i]) || isdigit(s[i])) {               // 如果是数字或者字母
            node n;
            n.data = islower(s[i]) ? toupper(s[i]) : s[i];  // 小写转大写
            n.index = i;
            handleS.push_back(n);
        }
    }
}

void updateIndex(int l, int h) {    // 更新最大长度回文子串的区间
    if (len > maxLen) {             // 有多个最大长度回文子串时,>选择最左边,>=选择最右边
        maxLen = len;
        low = l;
        high = h;
    }
}

void getDp() {
    len = maxLen = 1;
    low = high = 0;
    memset(dp, false, sizeof(dp));
    size = handleS.size();
    // 边界条件
    for (int i = 0; i < size; i++) {
        dp[i][i] = true;			// 单个字符构成的回文子串长度为1
        if (i < size - 1) {
            if (handleS[i].data == handleS[i + 1].data) {	// 若相邻两个字符相等
                dp[i][i + 1] = true;						// 构成长度为2的回文子串
                len = 2;
                updateIndex(handleS[i].index, handleS[i + 1].index);// 更新区间
            }
        }
    }

    for (int L = 3; L <= size; L++) {								// 枚举子串的长度
        for (int i = 0; i + L - 1 < size; i++) {					// 枚举子串的起始端点
            int j = i + L - 1;										// 子串的右端点
            // 两端相等且中间是回文串
            if (handleS[i].data == handleS[j].data && dp[i + 1][j - 1]) {
                dp[i][j] = dp[i + 1][j - 1];
                len = L;
                updateIndex(handleS[i].index, handleS[j].index);	// 更新区间
            }
        }
    }
}

int main() {
    while (cin.getline(s, MaxSize)) {
        handle();
        getDp();
        for (int i = low; i <= high; i++)	// 区间[low,high]即为回文子串在原字符串中的位置
            printf("%c", s[i]);
        printf("\n");
    }

    return 0;
}