题目传送门
很显然可以用 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;
}