P12213 [蓝桥杯 2023 国 Python B] 最长回文前后缀 题解 字符串哈希+二分

题目链接：https://www.luogu.com.cn/problem/P12213

解题思路

设字符串为 \(s\)，它的长度为 \(n\)。

我们用 \(s_i\) 表示字符串 \(s\) 的第 \(i\) 个字符，即 \(s = s_1 s_2 \ldots, s_n\)，

用 \(s[l..r]\) 表示子串 \(s_l s_{l+1} \ldots s_r\)。

设构成答案的是一个长度为 \(i\) 的前缀和一个长度为 \(j\) 的后缀。则：

如果 \(i \gt j\)，则：

• \(s[1..j]\)（长度为 \(j\) 的前缀） 和 \(s[n-j+1..n]\)（长度为 \(j\) 的后缀）是相反的字符串；
• \(s[j+1..i]\)（前缀中剩余的部分）是一个回文串

比如，下图演示了 \(s = \mathtt{abacadba}\)，\(i=5\)，\(j=2\) 时的情况。

如果 \(i \lt j\)，则：

• \(s[1..i]\)（长度为 \(j\) 的前缀） 和 \(s[n-i+1..n]\)（长度为 \(j\) 的后缀）是相反的字符串；
• \(s[n-j+1..n-i]\)（后缀中剩余的部分）是一个回文串

比如，下图演示了 \(s = \mathtt{acbcaacca}\)，\(i=2\)，\(j=6\) 时的情况。

\(i = j\) 时的情况可以归纳到上述两种情况中的任意一种。

所以我们可以先枚举前缀和后缀中那一段长度相同且相反的字符串的长度，然后再统计剩余字符能够构成的最长的回文串长度。

具体来说，如果长度为 \(i\) 的前缀和长度为 \(i\) 的后缀是相反的字符串。则

• 前缀接着可以加上 \(s_{i+1}\) 开头的最长回文串，或者
• 后缀接着可以机上 \(s_{n-i}\) （第倒数第 \(i+1\) 个字符）结尾的最长回文串

如果我们定义 \(f1_{i}\) 表示以 \(s_i\) 开头（包含 \(s_i\)）的最长回文子串长度，用 \(f2_i\) 表示以 \(s_i\) 结尾(包含 \(s_i\))的最长回文子串长度。

则答案为

\[\max\limits_{0 \le i \le n}( 2 \times i + \max(f1_{i+1}, f2_{n-i}) ) \]

其中：

• 必须要求字符串 \(s[1..i]\) 和 \(s[n-i+1..n]\) （即字符串 \(s\) 的长度为 \(i\) 的前缀和长度为 \(i\) 的后缀）是相反的字符串。

分析完了上述步骤之后，接下来要做的事情就是 枚举 \(i\)（\(i\) 表示 前缀/后缀 的长度），然后：

1. 判断长度为 \(i\) 的前缀和长度为 \(i\) 的后缀是否是相反的字符串；
   • 这个操作可以用 字符串哈希 实现
2. 求 \(f1_i\) 和 \(f2_{n-i}\) 的值。
   • 这个操作可以用 manacher 处理，总时间复杂度 \(O(n)\)
   • 也可以用 字符串哈希 + 二分 处理，总时间复杂度 \(O(n \log n)\)
   • 但是由于我 manacher 算法基本上忘了差不多了（主要每次都得再看一遍，然后再推一边，年纪大了容易忘），所以 接下来使用 字符串哈希 来实现（不用 manacher 了）

首先开两个用来保存哈希值的数组 \(h1\) 和 \(h2\)。其中：

• \(h1_i = s_1 \cdot B^1 + s_2 \cdot B^2 + \ldots + s_i \cdot B^i\)
• \(h2_i = s_i \cdot B^{n-i+1} + \ldots + s_{n-1} \cdot B^2 + s_n \cdot B^1\)

我们可以用递推式（\(h1_i = h1_{i-1} + s_i \cdot B^i\)，\(h2_i = h2_{i+1} + s_i \cdot B^{n-i+1}\)）\(O(n)\) 求出 \(h1\) 和 \(h2\) 数组。

则：

判断长度为 \(i\) 的前缀和长度为 \(i\) 的后缀是否是相反的字符串可以用如下等式：

\[h1_i = h2_{n-i+1} \]

判断字符串 \(s[l..r]\) 是否是回文串可以用如下表达式：

\[\frac{h1_r - h1_{l-1}}{B^{l-1}} = \frac{h2_l - h2_{r+1}}{B^{n-r}} \]

但是由于哈希要取模，所以最好不要出现除法（不然还得额外实现乘法逆元的逻辑），所以上述等式可以转换为

\[(h1_r - h1_{l-1}) \times B^{n-r} = (h2_l - h2_{r+1}) \times B^{l-1} \]

然后我们要枚举所有回文串的中心：

• 以 \(s_1\) 为中心（可能）的回文串只有 \(s[1..1]\)（这里加可能主要是因为这个子串不一定是回文串，还需要进行判断）
• 以 \(s_1,s_2\) 为中心（可能）的回文串只有 \(s[1..2]\)
• 以 \(s_2\) 为中心（可能）的回文串有 \(s[2..2]\)，\(s[1..3]\)
• 以 \(s_2,s_3\) 为中心（可能）的回文串有 \(s[2..3]\)，\(s[1..4]\)
• 以 \(s_3\) 为中心（可能）的回文串有 \(s[3..3]\)，\(s[2..4]\)，\(s[1..5]\)
• ……

我们可以二分快速找到以某一个 \(s_i\)（或者 \(s_i, s_{i+1}\)） 为中心的回文串的最大半径。

• 如果以 \(s_i\) 为中心的回文串的最大半径为 \(d\)，则以 \(s_i\) 为中心的最长回文串为 \(s[i-d..i+d]\)
• 如果以 \(s_i, s_{i+1}\) 为中心的回文串的最大半径为 \(d\)，则以 \(s_i, s_{i+1}\) 为中心的最长回文串为 \(s[i-d..i+1+d]\)

所以，对于下标 \(p\)

• 如果 \(p\) 处于以 \(s_i\) 为中心的回文串的右侧，则以 \(s_i\) 为中心，\(s_p\) 为右端点的回文串的长度为 \(2 \cdot (p-i) + 1\)
• 如果 \(p\) 处于以 \(s_i, s_{i+1}\) 为中心的回文串的右侧，则以 \(s_i, s_{i+1}\) 为中心，\(s_p\) 为右端点的回文串的长度为 \(2 \cdot (p-i)\)

而且我们会发现，\(i\) 越小，则以 \(s_p\) 为右端点的回文串长度越大。\(\Rightarrow\) 所以我们从事用最小的 \(i\) 来覆盖它能够覆盖到的最大的 \(p\)。

按照这样一个逻辑我们就能求出 \(f1\) 数组。时间复杂度 \(O(n \log n)\)。

同样的逻辑反着就能求出 \(f2\) 数组。

以下是完整的代码：

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn = 2e5 + 5;
const ull B = 233;int n, d[maxn], f1[maxn], f2[maxn];
ull h1[maxn], h2[maxn], fac[maxn] = {1};
char s[maxn], a[maxn];void init() {for (int i = 1, j = n; i <= n; i++, j--) {fac[i] = fac[i-1] * B;h1[i] = h1[i-1] + (s[i] - 'a' + 1) * fac[i];h2[j] = h2[j+1] + (s[j] - 'a' + 1) * fac[i];}
}// 判断 s[l..r] 是不是回文串
bool check(int l, int r) {ull res1 = (h1[r] - h1[l-1]) * fac[n-r];ull res2 = (h2[l] - h2[r+1]) * fac[l-1];return res1 == res2;
}int get_d(int x, int y) {int l = 0, r = min(x-1, n-y), res = 0;while (l <= r) {int mid = (l + r) / 2;if (check(x-mid, y+mid))res = mid, l = mid + 1;elser = mid - 1;}return res;
}int cal() {int res = max(f2[1], f1[n]);for (int i = 1, j = n; i <= n; i++, j--) {if (h1[i] == h2[j])res = max(res, 2*i + max(f2[i+1], f1[n-i]));}return res;
}int main() {scanf("%s", s+1);n = strlen(s+1);init();for (int i = 1, p = 0; i <= n; i++) {int q = i + get_d(i, i);while (p <= q) f1[p] = 2*(p-i)+1, p++;if (i < n && s[i] == s[i+1]) {q = i+1 + get_d(i, i+1);while (p <= q) f1[p] = 2*(p-i), p++;}}for (int i = n, p = n; i >= 1; i--) {int q = i - get_d(i, i);while (p >= q) f2[p] = 2*(i-p)+1, p--;if (i > 1 && s[i-1] == s[i]) {q = i-1 - get_d(i-1, i);while (p >= q) f2[p] = 2*(i-p), p--;}}printf("%d\n", cal());return 0;
}