题目链接：UOJ 219
如果一个字符串可以被拆分为 $\text{AABB}$ 的形式，其中 $\text{A}$ 和 $\text{B}$ 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。
例如，对于字符串 $ \texttt{aabaabaa} $ ，如果令 $\text{A}=\texttt{aab}$，$\text{B}=\texttt{a}$，我们就找到了这个字符串拆分成 $\text{AABB}$ 的一种方式。
一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。
比如我们令 $\text{A}=\texttt{a}$，$\text{B}=\texttt{baa}$，也可以用 $\text{AABB}$ 表示出上述字符串；但是，字符串 $\texttt{abaabaa}$ 就没有优秀的拆分。
现在给出一个长度为 $n$ 的字符串 $S$，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。
以下事项需要注意：
- 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
- 在一个拆分中，允许出现 $\text{A}=\text{B}$。例如 $\texttt{cccc}$ 存在拆分 $\text{A}=\text{B}=\texttt{c}$。
- 字符串本身也是它的一个子串。
本题有 $T$ 组数据。
数据范围：$1 \le T \le 10$，$1 \le n \le 3 \times 10 ^ 4$。
Solution
由于在 $\text{AABB}$ 中，前面的 $\text{AA}$ 和后面的 $\text{BB}$ 是两个独立的部分，其形式均为 $\text{AA}$。那么我们分别考虑这些贡献，最后统计答案。
设 $f(i), g(i)$ 分别 表示第 $i$ 个位置往前、往后分别有多少个形如 $\text{AA}$ 的子串。那么答案为：
$$ \sum_{i = 1} ^ {n - 1} f(i) \cdot g(i +1) $$
现在的问题就是如何求 $f(i), g(i)$。考虑一种最暴力的方法：枚举位置，枚举往前、往后的子串。通过 $\text{Hash}$ 显然可以得到一种 $\mathcal O(n ^ 2)$ 的做法。
考虑如何优化。我们使用一种数论中常用的手法：变换枚举顺序，先枚举长度，再计算哪些位置会产生贡献。
假设当前枚举的 $\text{AA}$ 的长度为 $2L$，我们以 $L$ 为步长放置关键点（也就是在 $L, 2L, 3L, \dots $ 放置关键点），可以发现，对于任意一个长度为 $2L$ 的子串，必定会覆盖 $2$ 个关键点。因此可以枚举相邻两个关键点 $i, j$，求出 $\text{prefix}(i), \text{prefix}(j)$ 的 $\text{LCS} = x$ 和 $\text{suffix}(i), \text{suffix}(j)$ 的 $\text{LCP} = y$。可以通过后缀数组求得。
接下来的内容需要读者自己画图理解。当 $x + y - 1 < L$ 时，可以证明长度为 $2L$ 的 $\text{AA}$ 子串不可能经过 $i, j$ 两点。否则会产生贡献的点是一段区间，直接差分统计贡献。
由于枚举长度和关键点的复杂度为调和级数，因此单次询问复杂度为 $\mathcal O(n \log n)$。
时间复杂度：$\mathcal O(T \cdot n \log n)$
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 3e4 + 5;
int T, n, f[N], g[N];
char s[N];
template <int MAX>
struct SuffixArray {
static const int N = MAX, logN = 15;
int n, m, sa[N], rk[N], cnt[N], tmp[N], height[N], lg[N], f[N][logN];
void radixSort() {
std::fill(cnt + 1, cnt + m + 1, 0);
for (int i = 1; i <= n; i++) cnt[rk[i]]++;
for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i--) sa[cnt[rk[tmp[i]]]--] = tmp[i];
}
template <typename Tp>
void build(Tp *a, int _n, int _m) {
n = _n, m = _m;
for (int i = 1; i <= n; i++) rk[i] = a[i], tmp[i] = i;
radixSort();
for (int l = 1, p = 0; p < n; l <<= 1, m = p) {
p = 0;
for (int i = n - l + 1; i <= n; i++) tmp[++p] = i;
for (int i = 1; i <= n; i++) if (sa[i] > l) tmp[++p] = sa[i] - l;
radixSort();
std::swap(rk, tmp);
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
int u = sa[i - 1], v = sa[i];
int uu = (u + l <= n ? u + l : 0), vv = (v + l <= n ? v + l : 0);
rk[sa[i]] = (tmp[u] == tmp[v] && tmp[uu] == tmp[vv] ? p : ++p);
}
}
a[n + 1] = 0;
for (int i = 1, k = 0; i <= n; i++) {
k -= (k > 0);
int j = sa[rk[i] - 1];
for (; a[i + k] == a[j + k]; k++);
height[rk[i]] = k;
}
}
void buildRMQ() {
for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= n; i++) f[i][0] = height[i];
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
f[i][j] = std::min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int l, int r) {
int k = lg[r - l + 1];
return std::min(f[l][k], f[r - (1 << k) + 1][k]);
}
int lcp(int i, int j) {
i = rk[i], j = rk[j];
if (i == j) return n - sa[i] + 1;
if (i > j) std::swap(i, j);
return query(i + 1, j);
}
};
SuffixArray<N> S1, S2;
int lcp(int i, int j) {
return S1.lcp(i, j);
}
int lcs(int i, int j) {
return S2.lcp(n - i + 1, n - j + 1);
}
int main() {
scanf("%d", &T);
for (int cs = 1; cs <= T; cs++) {
scanf("%s", s + 1);
n = strlen(s + 1);
S1.build(s, n, 255), S1.buildRMQ();
std::reverse(s + 1, s + n + 1);
S2.build(s, n, 255), S2.buildRMQ();
std::fill(f + 1, f + n + 1, 0);
std::fill(g + 1, g + n + 1, 0);
for (int l = 1; l <= (n >> 1); l++) {
for (int i = l, j = l + l; j <= n; i += l, j += l) {
int x = std::min(lcs(i, j), l), y = std::min(lcp(i, j), l);
if (x + y - 1 < l) continue;
f[j + l - x]++, f[j + y]--;
g[i - x + 1]++, g[i + y - l + 1]--;
}
}
for (int i = 1; i <= n; i++) {
f[i] += f[i - 1], g[i] += g[i - 1];
}
long long ans = 0;
for (int i = 1; i < n; i++) ans += 1LL * f[i] * g[i + 1];
printf("%lld\n", ans);
}
return 0;
}