题目分析

我们有两个字符串 $s_1$ 和 $s_2$，要求从 $s_1$ 中取一个子串，从 $s_2$ 中取一个子串，这两个子串相同，求不同的方案数。

例如：

s1 = "aabb"
s2 = "bbaa"

相同子串的情况：

• 长度 1：'a' 和 'a'，'b' 和 'b' 的各种位置组合
• 长度 2：'aa' 和 'aa'，'bb' 和 'bb' 的各种位置组合
• 长度 3 及以上：没有

最后统计得到 10 种方案。

思路

暴力法（不可行）

枚举 $s_1$ 的所有子串起点 $i$，$s_2$ 的所有子串起点 $j$，然后枚举长度 $L$ 直到不相等为止。复杂度 $O(n_1 n_2 \cdot L)$ 不可接受。

后缀数组 / 后缀自动机方法

一个常用技巧：
所有公共子串的数量可以通过后缀自动机（SAM）或后缀数组（SA）计算。

后缀自动机（SAM）解法

我们可以用 广义后缀自动机（GSAM） 或者分别建 SAM 再用后缀树（parent 树）统计。

步骤：

1. 把 $s_1$ 和 $s_2$ 用特殊字符连接起来，得到 $s = s_1 + \# + s_2$（# 是不在字母表中的分隔符）。
2. 对 $s$ 建立后缀自动机。
3. 在自动机的每个状态节点上，记录两个信息：
   • cnt1：该状态代表的子串在 $s_1$ 中出现的次数
   • cnt2：该状态代表的子串在 $s_2$ 中出现的次数
4. 在 parent 树上做 DFS 或按拓扑序累加 cnt1 和 cnt2。
5. 对于每个状态节点，它对答案的贡献是：$$\text{len}(p) - \text{len}(\text{link}(p)) \times \text{cnt1}[p] \times \text{cnt2}[p] $$其中 $\text{len}(p)$ 表示该状态能表示的最长子串长度，$\text{len}(\text{link}(p))$ 是后缀链接指向的状态的最长子串长度。差值就是这个状态独有的子串长度范围，这些子串在 $s_1$ 中出现 cnt1[p] 次，在 $s_2$ 中出现 cnt2[p] 次，所以这些子串作为公共子串的方案数为 $\text{diff} \times \text{cnt1}[p] \times \text{cnt2}[p]$。

复杂度

• 构建 SAM：$O(n)$
• 统计 cnt1, cnt2：$O(n)$
• 总复杂度 $O(n_1 + n_2)$，适合 $2\times 10^5$ 数据范围。