检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。
题面
题目描述
顺序和逆序读起来完全一样的串叫做回文串。比如 acbca
是回文串,而 abc
不是(abc
的顺序为 abc
,逆序为 cba
,不相同)。
输入长度为 的串 ,求 的最长双回文子串 ,即可将 分为两部分 ()且 和 都是回文串。
输入格式
一行由小写英文字母组成的字符串 。
输出格式
一行一个整数,表示最长双回文子串的长度。
输入输出样例
样例输入 #1
baacaabbacabb
样例输出 #1
12
样例解释 #1
从第二个字符开始的字符串 aacaabbacabb
可分为 aacaa
与 bbacabb
两部分,且两者都是回文串。
数据范围与约定
对于 的数据,。
思路
刚拿到这道题的时候,一下子有了一个偏朴素的做法:先跑一遍 Manacher,然后对于每个点分别枚举以它为左右端点的回文串相加取最大值。又去看了眼数据范围,仔细一想发现这个做法实际复杂度是 的,无法通过本题。
可以设 表示以 为左端点的最长的回文串, 表示以 为右端点的最长的回文串。有转移方程如下:
然后再递推将前/后方的最长回文串转移过来。因为两个回文串不能重叠,所以每次选择分隔符 #
进行枚举,就避免了重叠的问题,转移方程如下:
之后再次枚举每个断点更新答案即可。
代码
#include <iostream>
#include <string>
using std::cin;
using std::cout;
const char endl = '\n';
const int N = 1e5 + 5;
int mid, r, p[N << 1], a[N << 1], b[N << 1], ans;
std::string s1, s2;
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s1;
s2.push_back('^');
for (const char &c : s1) {
s2.push_back('#');
s2.push_back(c);
}
s2 += "#$";
for (int i = 1; i < s2.size(); i++) {
p[i] = i < r ? std::min(p[mid * 2 - i], r - i) : 1;
while (s2[i - p[i]] == s2[i + p[i]]) p[i]++;
if (i + p[i] > r) {
r = i + p[i];
mid = i;
}
a[i + p[i] - 1] = std::max(a[i + p[i] - 1], p[i] - 1);
b[i - p[i] + 1] = std::max(b[i - p[i] + 1], p[i] - 1);
}
for (int i = s2.size() - 4; i >= 3; i -= 2) {
a[i] = std::max(a[i], a[i + 2] - 2);
}
for (int i = 3; i <= s2.size() - 4; i += 2) {
b[i] = std::max(b[i], b[i - 2] - 2);
}
for (int i = 3; i <= s2.size() - 4; i += 2) {
ans = std::max(ans, a[i] + b[i]);
}
cout << ans << endl;
return 0;
}