P9873 [EC Final 2021] Beautiful String
Autream
·
·
题解
题目要求形如 AABCAB 的子串的个数。观察到其中有两个 AB，考虑去枚举第一个 AB，那么满足要求的子串就是 AB 前面紧跟着一个它的前缀，在它后面还有一个 AB 不与它相邻。
设第一个 AB 的第一个字符在位置 i，第二个 AB 的第一个字符在位置 j，l_1 = |A|, l_2 = |AB|，为了保证 A 非空，l_1 < l_2。
那么前后能匹配的最大长度就是 ma = \min \{j - i - 1, lcp_{i, j}\}，其中 lcp_{i, j} 表示以 i 开头的后缀和以 j 开头的后缀的最长公共前缀，可以 O(n ^ 2) 预处理，j - i - 1 是因为要保证它们不相邻，所以长度最大为这么多。
答案即为：
\sum _i \sum _j \sum _{l_2 = 1} ^{ma} \sum _{l_1 = 1} ^{l_2 - 1} [lcp_{i - l_1, i} \ge l_1]
将内层循环展开：
$$
\begin{aligned}
\sum _{l_1 = 1} ^{ma - 1} (ma - l_1)\times [lcp_{i - l_1, i} \ge l_1]
\end{aligned}
$$
继续展开并整理可得原式是以下项的和：
$$
\begin{aligned}
&l_1 = 1: [lcp_{i - 1, i} \ge 1] \\
&l_1 = 2: [lcp_{i - 1, i} \ge 1], [lcp_{i - 2, i} \ge 2] \\
&l_1 = 3: [lcp_{i - 1, i} \ge 1], [lcp_{i - 2, i} \ge 2], [lcp_{i - 3, i} \ge 3] \\
\vdots \\
&l_1 = ma - 1: [lcp_{i - 1, i} \ge 1], [lcp_{i - 2, i} \ge 2], [lcp_{i - 3, i} \ge 3] , \dots, [lcp_{i - ma + 1, i} \ge ma - 1]
\end{aligned}
$$
应该很好想了，发现每一行行内可以前缀和优化，之后再将每一行做前缀和。
具体地，设
$$
\begin{aligned}
&f_{i, j} = \sum \limits _{k = 1} ^j [lcp_{i - k, i} \ge j] \\
&g_{i, j} = \sum _{k = 1} ^ j (j - k + 1) \times [lcp_{i - k, i} \ge k] = \sum \limits _{k = 1} ^j f_{i, k}
\end{aligned}
$$
最后答案为 $\sum \limits _i \sum \limits _j g_{i, ma - 1}$，注意越界处理。
时间复杂度 $O(n ^ 2)$。
## 代码
```cpp
CI N = 5e3 + 5;
int n, ans, lcp[N][N], f[N][N], g[N][N];
std::string s;
signed main() {
int T = read();
while(T --) {
std::cin >> s, n = s.size(), s = " " + s, ans = 0;
dep(i, n, 1) dep(j, n, i) if(s[i] == s[j]) lcp[i][j] = lcp[i + 1][j + 1] + 1;
rep(i, 1, n) rep(j, 1, n) f[i][j] = i - j >= 0 ? f[i][j - 1] + (lcp[i - j][i] >= j) : f[i][i];
rep(i, 1, n) rep(j, 1, n) g[i][j] = g[i][j - 1] + f[i][j];
rep(i, 2, n) rep(j, i + 3, n - 1) ans += g[i][std::max(1ll, std::min(j - i - 1, lcp[i][j])) - 1];
printl(ans);
rep(i, 1, n) rep(j, 1, n) lcp[i][j] = f[i][j] = g[i][j] = 0;
}
return 0;
}
```