题目传送门
很显然可以用 manacher 做。
根据题意,要忽略所有特殊符号,只保留字母,所以要把初始化改一改。

如何还原字符串?只需要拿一个数组记录位置就好了。(如下面代码中的 pos 数组)

#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e4 + 5;
char str[maxN], expa[maxN << 1];
int r[maxN << 1], pos[maxN << 1];
int ans, len, n, cur;
void read() {
    len = 0;
    while ((str[len] = getchar()) != EOF) len++;
    // 因为毒瘤数据还会换行,所以用这种玄学读法
}
void init() {
    n = 0;
    expa[0] = expa[1] = '#';
    for (int i = 0; i < len; i++) {
        if (isalpha(str[i])) { // 如果是字母
        // cctype 头文件里的库,下面的 tolower 也是
            expa[n * 2 + 2] = tolower(str[i]); // 大写转小写,小写不转
            expa[n * 2 + 3] = '#';
            pos[n * 2 + 2] = i; // pos 对应记录原字符串位置
            n++;
        }
    }
    n = n * 2 + 4;
    expa[n] = '$';
}
void manacher() {
    int maxright = 0, mid = 0;
    for (int i = 1; i < n; i++) {
        if (i < maxright)
            r[i] = min(r[(mid << 1) - i], r[mid] + mid - i);
        else r[i] = 1;
        while (expa[i + r[i]] == expa[i -r[i]]) r[i]++;
        if (r[i] + i > maxright) {
            maxright = r[i] + i;
            mid = i;
        }
    }
    int tmp = 1;
    for (int i = 0; i < n; i++)
        if (r[i] > tmp) {
            tmp = r[i];
            cur = i; // 记录最大半径位置
        }
    --tmp;
    cout << tmp << endl; // 以上是 manacher 主过程
    --tmp; // 半径是扩展后字符串回文串的半径,-1 是因为要除去对称轴(看下面的循环体)
    for (int i = pos[cur - tmp]; i <= pos[cur + tmp]; i++)
        printf("%c", str[i]);
}
int main() {
    read();
    init();
    manacher();
    return 0;
}