题目理解

我们要求的是：对于字符串 $S$ 的每一个子串，统计它有多少种优秀的拆分，然后把所有子串的优秀拆分个数加起来。

一个优秀的拆分是：子串可以写成 $\text{AABB}$ 形式，其中 $\text{A}$ 和 $\text{B}$ 非空。

思路分析

1. 暴力方法

枚举所有子串 $S[i..j]$，再枚举拆分点，判断是否满足 $\text{AABB}$ 形式。
复杂度 $O(n^4)$ 或 $O(n^3)$，显然不可行。

2. 转化问题

$\text{AABB}$ 可以看作两个 $\text{AA}$ 形式的串拼接而成，中间切一刀：
设切点在 $p$ 和 $p+1$ 之间，那么前半部分 $S[1..p]$ 的某个后缀是 $\text{AA}$，后半部分 $S[p+1..n]$ 的某个前缀是 $\text{BB}$。

更精确地，对于一个固定的切分位置 $p$（即 $\text{AABB}$ 中第一个 $\text{B}$ 开始的位置的前一个位置），我们要数有多少对 $(A,B)$ 使得：

• $S[p-2|A|+1 .. p] = \text{AA}$
• $S[p+1 .. p+2|B|] = \text{BB}$

这样还是复杂，我们换一种思路。

3. 关键观察

$\text{AABB}$ 可以看作在某个位置 $i$ 切分，左边是 $\text{AA}$ 的结束位置，右边是 $\text{BB}$ 的开始位置。

具体来说，设 $p$ 是第一个 $\text{B}$ 的开头位置的前一个位置（即 $\text{AA}$ 的结尾位置），那么：

• 在 $p$ 处结束的形如 $\text{XX}$ 的串的个数，记作 $f(p)$
• 在 $p+1$ 处开始的形如 $\text{XX}$ 的串的个数，记作 $g(p+1)$

那么以 $p$ 为 $\text{AA}$ 与 $\text{BB}$ 的分界点，优秀拆分的个数就是 $f(p) \times g(p+1)$。

因此，问题转化为：

1. 对每个位置 $i$，计算有多少个 $\text{AA}$ 以 $i$ 结尾 → $f(i)$
2. 对每个位置 $i$，计算有多少个 $\text{AA}$ 以 $i$ 开头 → $g(i)$
3. 答案 $= \sum_{p=1}^{n-1} f(p) \cdot g(p+1)$

4. 如何求 $f(i)$ 和 $g(i)$

求所有 $\text{AA}$ 型子串的出现位置，是一个经典问题。

方法： 使用后缀数组 (Suffix Array) + 高度数组 (LCP) 或 哈希 + 枚举长度。

枚举长度法

枚举 $\text{AA}$ 的长度 $len$，那么 $\text{AA}$ 由两个相同子串拼接，中间切点在某个位置。

我们枚举 $len$，然后在字符串上以步长 $len$ 设置关键点，相邻关键点求最长公共前缀 (LCP) 和最长公共后缀 (LCS)，就可以得到 $\text{AA}$ 出现的区间。

具体做法（常见套路）：

• 设关键点为 $k \cdot len$ 和 $(k+1)\cdot len$
• 计算 $LCP(s[k\cdot len .. n], s[(k+1)\cdot len .. n])$ 和 $LCS(s[1 .. k\cdot len], s[1 .. (k+1)\cdot len])$
• 通过 LCP 和 LCS 可以确定 $\text{AA}$ 覆盖的区间，然后用差分数组标记这些 $\text{AA}$ 的起始和结束位置。

这样我们就能得到：

• 以 $i$ 结尾的 $\text{AA}$ 个数 $f(i)$
• 以 $i$ 开头的 $\text{AA}$ 个数 $g(i)$

5. 复杂度

枚举 $len$ 从 $1$ 到 $n$，内部 $O(n/len)$ 个关键点，每个关键点求 LCP/LCS 如果用哈希+二分是 $O(\log n)$，总复杂度 $O(n \log^2 n)$，可过 $n \le 30000$。

如果用后缀数组 + ST 表求 LCP，可以做到 $O(n \log n)$。

6. 算法步骤

1. 读入多组数据。
2. 对每组数据：
   • 初始化 $f[1..n] = 0$, $g[1..n] = 0$
   • 枚举 $len = 1$ 到 $n/2$：
     • 对 $k = 0,1,\dots$ 且 $(k+1)len \le n$：
       • 计算 $LCP(k\cdot len+1, (k+1)\cdot len+1)$
       • 计算 $LCS(k\cdot len, (k+1)\cdot len)$
       • 确定 $\text{AA}$ 出现的区间，更新 $f$ 和 $g$ 的差分数组
   • 对差分数组求前缀和得到真正的 $f$ 和 $g$
   • 计算 $\sum_{p=1}^{n-1} f(p) \cdot g(p+1)$，输出答案