P9543 [湖北省选模拟 2023] 日记 / diary
Alex_Wei
·
·
题解
*P9543 [湖北省选模拟 2023] 日记 / diary
相当酷的一道题目。
设 n = |S|，m = |T|。
首先让我们思考线性时间能求出哪些信息。KMP，扩展 KMP，Manacher，Lyndon 分解，最小表示法等字符串算法都是可以接受的，不过至于 SA，SAM 这样的后缀数据结构就别想了。因为本题和回文与字典序没有太大关系，而和 “一个字符串在另一个字符串中出现” 密切相关，所以我们猜测本题的主要算法是 KMP 和扩展 KMP。
不妨将限制放宽一些。如果不要求得到的字符串包含 $T$ 作为子串，能做吗？**必须能**。构造 $|T| = 1$ 且 $S_1 = S_n = T_1$，可知原问题不弱于：任选 $S$ 的可空前缀 $P$ 与可空后缀 $Q$，求本质不同的 $P + Q$ 的数量。
该问题容易在线性时间内解决：对于每个本质不同的 $R = P + Q$，只在最后一个分割点处统计它，即枚举 $R$ 与 $S$ 的最长公共前缀长度 $L$，并认为 $P = S_{1\sim L}$。因此，对于每个 $P$，所有合法的 $Q$ 形如：若 $P = S$，则 $Q$ 为任意后缀；若 $P\neq S$ 即 $L < n$，则 $|Q| = 0$ 或 $Q_1 \neq S_{L + 1}$，否则 $S$ 与 $R$ 的最长公共前缀还可以更长，即 $L$ 可以更大。用总数 $(n + 1) ^ 2$ 减去对每个 $0 \leq L < N$，第一个字符等于 $S_{L + 1}$ 的非空后缀数量，即字符 $S_{L + 1}$ 在 $S$ 中出现的次数。
尝试加入 $T$ 在 $R$ 中出现的限制，有三种情况：$T$ 在 $P$ 中出现；$T$ 在 $Q$ 中出现；$T$ 等于 $P$ 的非空后缀加上 $Q$ 的非空前缀。但这三种情况可能同时发生，再加上本质不同的要求，根本无从下手。但很显然，$T$ 在 $P$ 或 $Q$ 中出现的情况更容易考虑一些，因为它只与 $P$ 或 $Q$ 相关，而不同时与 $P, Q$ 相关。我们希望尽可能排除这两种情况，简化问题。
先看看用上面的算法能推出哪些东西吧：设 $f(i, j)$ 表示不要求 $T$ 在 $R$ 中出现过，$|P| \leq i$ 且 $|Q|\leq n - i + 1$ 的本质不同的 $R$ 的数量，可以线性计算。容斥是必要的。首先用 $f(n, 1)$ 估计答案，但是多算了不包含 $T$ 的 $R$。只要 $P$ 或 $Q$ 包含 $T$，那么 $R$ 一定包含 $T$。故考虑设 $T$ 在 $S$ 中第一次出现的 **结束位置** 为 $c$，最后一次出现的 **开始位置** 为 $d$，若 $P$ 的结束位置在 $c$ 及其右侧，或 $Q$ 的开始位置在 $d$ 及其左侧，那么 $R$ 一定包含 $T$。特别地，若 $T$ 没有在 $S$ 中出现，可认为 $c = n + 1$，$d = 0$。
在容斥减去不包含 $T$ 的 $R$ 的数量时，可以限制 $|P| < c$ 且 $|Q| < n - d + 1$。用 $f(c - 1, d + 1)$ 估计这个值，将导致答案少算了 **存在** 分割方式使得 $|P| < c$ 且 $|Q| < n - d + 1$ 的包含 $T$ 的 $R$ 的数量。
将 $c$ 减去 $1$，$d$ 加上 $1$，我们将问题转化为了：计算 $P$ 的结束位置在 $c$ 及其左侧，$Q$ 的结束位置在 $d$ 及其右侧，且 $T$ 在 $R$ 中出现过的本质不同的 $R$ 的数量。根据 $c$ 和 $d$ 的定义，可知 $P$ 和 $Q$ 不可能单独包含 $T$。因此，$T$ 必然等于 $P$ 的某个 **非空** 后缀加上 $Q$ 的某个 **非空** 前缀。在这个前提下，关于 “$T$ 在 $R$ 中出现” 的限制，有两种思路：
**思路一**：枚举 $|P|$，那么合法的 $Q$ 满足：存在 $L$ 使得 $P$ 的长度为 $L$ 的后缀等于 $T$ 的长度为 $L$ 的前缀，且 $Q$ 的长度为 $n - L$ 的前缀等于 $T$ 的长度为 $n - L$ 的后缀。
- 刻画 $L$ 的形态：建出 $T$ 的失配树，设 $P$ 与 $T$ 的最长公共后缀前缀为 $len$（KMP 求出），那么 $L$ 是失配树上 $len$ 的祖先。
- 刻画 $Q$ 的形态：建出 $T$ 的反串的失配树，设 $Q$ 与 $T$ 的最长公共前缀后缀为 $len$，那么 $n - L$ 是失配树上 $len$ 的祖先。固定 $L$，合法的 $Q$ 是 $T$ 的反串的失配树的某棵子树。因此合法的 $Q$ 是该失配树的若干子树的并，这很难处理，更何况还有本质不同的限制。这种思路并不可行。
**思路二**：从 $R$ 中删去 $T$，设 $P$ 和 $Q$ 变成了 $P'$（$P'$ 是 $P$ 的前缀，且 $P' \neq P$）和 $Q'$（$Q'$ 是 $Q$ 的后缀，且 $Q'\neq Q$），枚举 $L = |P'|$，设 $S_{L + 1\sim c}$ 与 $T$ 的最长公共前缀为 $x$，那么要求 $S_{d\sim n - |Q'|}$ 与 $T$ 的最长公共后缀 $y\geq m - x$。
先不管本质不同，合法的 $(P', Q')$ 二元组数量是可以计算的：对每个 $1\leq i\leq c$，使用扩展 KMP 求出 $S_{i\sim c}$ 与 $T$ 的最长公共前缀 $zs_i$；对每个 $d\leq j\leq n$，使用扩展 KMP 求出 $S_{d\sim j}$ 与 $T$ 的最长公共后缀 $zs'_j$。注意到 $zs$ 和 $zs'$ 均小于 $m$，所以 $P'$ 不会以位置 $c$ 结尾（否则要求 $Q$ 完全包含 $T$），同理 $Q'$ 不会以位置 $d$ 开头。因此，合法的 $(P', Q')$ 二元组数量就等于 $\sum_{i = 1} ^ c\sum_{j = d} ^ n [zs_i + zs'_j \geq m]$。这是一维偏序，复杂度线性。
加入本质不同的限制，我们希望在最小的 $|P'|$ 的位置统计 $R$。不能存在 **合法** 的 $(P'', Q'')$ 使得 $P'' + T + Q'' = P' + T + Q'$ 且 $|P''| < |P'|$，为此，尝试探究什么样的 **合法** 二元组需 $(P', Q')$ 要舍去。
考虑两个 **合法** 二元组 $(P_1', Q_1')$ 和 $(P_2', Q_2')$ 满足 $R = P_1' + T + Q_1' = P_2' + T + Q_2'$。不妨设 $|P_1'| < |P_2'|$，则 $(P_2', Q_2')$ 需要被舍去。设 $per = |P_2'| - |P_1'|$，则 $per < m$（否则 $T$ 在 $P_2'$ 中出现）。
- 根据 $P_1' + T + Q_1' = P_2' + T + Q_2'$，可知 $P_2'$ 与 $T$ 有长度为 $per$ 的公共后缀前缀，且 $Q_1'$ 与 $T$ 有长度为 $per$ 的公共前缀后缀。又因为 $Q_1'$ 的起始位置在 $d$ 及其右侧，所以后者等价于 $S_{d\sim n - |Q_2'|}$ 与 $T$ 有长度为 $per$ 的公共后缀，即 $zs'_{n - |Q_2'|} \geq per$。
- 设 $R = P_1' + T' + Q_2'$，那么 $|T'| = m + per$ 且 $T$ 为 $T'$ 的 border。这说明 $T'$ 有长度为 $per$ 的 period，继而推出 $T$ 有长度为 $per$ 的 period。
综上，得 $(P_2', Q_2')$ 需要被舍去的必要条件：存在 $per$ 同时满足
- $per$ 是 $T$ 的 period。
- $P_2'$ 与 $T$ 有长度为 $per$ 的公共后缀前缀。
- $zs'_{n - |Q_2'|} \geq per$。
充分吗？充分性是容易证明的。
枚举 $|P_2'|$。显然我们只关心最小的 $per$ 使得 $per$ 是 $T$ 的 period 且 $P_2'$ 与 $T$ 有长度为 $per$ 的公共后缀前缀，因为对于所有这样的 $per$，如果 $zs'_{n - |Q_2'|}$ 小于最小的 $per$，那么更大的 $per$ 也不会让它被舍去。
综上，枚举 $0\leq i = |P'| < c$，求出对应的最小的 $per$（标记所有 period，然后在失配树上 DP），合法的 $Q'$ 的起始位置 $d < j \leq n + 1$ 满足：
- $zs_{i + 1} + zs'_{j - 1} \geq m$。
- $zs'_{j - 1} < per$。
看上去是二维偏序，但这就是 $m - zs_{i + 1} \leq zs'_{j - 1} < per$，还是一维偏序，前缀和即可。
时间复杂度 $\mathcal{O}(n + m)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool Mbe;
constexpr int N = 1e7 + 5;
ll ans;
int n, m, f[N], fst = -1, lst = -1;
int zs[N], _zs[N], zt[N];
int ns[N], nt[N], buc[N];
char s[N], t[N];
void calcnxt(int *nt, int *ns) {
for(int i = 2; i <= m; i++) {
int j = nt[i - 1];
while(j && t[j + 1] != t[i]) j = nt[j];
nt[i] = j + (t[j + 1] == t[i]);
}
for(int i = 1; i <= n; i++) {
int j = ns[i - 1];
while(j && t[j + 1] != s[i]) j = nt[j];
ns[i] = j + (t[j + 1] == s[i]);
}
}
void calcz(int *zt, int *zs) {
int l = 1, r = 0;
for(int i = 2; i <= m; i++) {
int j = i > r ? 0 : min(zt[i - l + 1], r - i + 1);
while(t[j + 1] == t[i + j]) j++;
if(i + j > r) l = i, r = i + j - 1;
zt[i] = j;
}
l = 1, r = 0;
for(int i = 1; i <= n; i++) {
int j = i > r ? 0 : min(zt[i - l + 1], r - i + 1);
while(i + j <= n && t[j + 1] == s[i + j]) j++;
if(i + j > r) l = i, r = i + j - 1;
zs[i] = j;
}
}
ll calc(int l, int r) {
ll res = 1ll * (l + 1) * (n - r + 2);
vector<int> cnt(26);
for(int i = r; i <= n; i++) cnt[s[i] - 'a']++;
for(int i = 1; i <= l; i++) res -= cnt[s[i] - 'a'];
return res;
}
bool Med;
int main() {
fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
#ifdef ALEX_WEI
FILE *IN = freopen("diary.in", "r", stdin);
FILE *OUT = freopen("diary.out", "w", stdout);
#endif
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> s + 1 >> t + 1;
n = strlen(s + 1), m = strlen(t + 1);
calcz(zt, _zs);
reverse(s + 1, s + n + 1);
reverse(_zs + 1, _zs + n + 1);
reverse(t + 1, t + m + 1);
calcz(zt, zs), calcnxt(nt, ns);
for(int i = 0; i <= m; i++) f[i] = m;
for(int i = nt[m]; i; i = nt[i]) f[m - i] = m - i;
for(int i = 1; i <= m; i++) f[i] = min(f[i], f[nt[i]]);
for(int i = m; i <= n; i++) if(ns[i] == m) fst == -1 && (fst = i - 1), lst = i - m + 2;
if(fst != -1) ans = calc(n, 1) - calc(fst, lst);
else fst = n, lst = 1;
for(int i = 1; i <= fst; i++) zs[i] = min(zs[i], fst - i + 1);
for(int i = lst; i <= n; i++) buc[_zs[i] = min(_zs[i], i - lst + 1)]++;
for(int i = 1; i <= n; i++) buc[i] += buc[i - 1];
for(int i = 1; i <= fst; i++) {
int l = m - zs[i], r = min(n, f[ns[i - 1]] - 1);
if(l <= r) ans += buc[r] - buc[l - 1];
}
cout << ans << "\n";
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
/*
g++ diary.cpp -o diary -O2 -std=c++14 -DALEX_WEI
*/
```