广义 SAM 上每个模板串包含的节点数量和的上界以及构造

Update On 20210120：发现自己各种乱用 \(O\)，修改了一下。

做 cmd 的某字符串题 的时候写了个复杂度基于标题的算法，当时以为这是线性的。后来看题解里有人写是 \(1.5\) 次方的，就仔细思考了一下。后来感觉这东西挺简单的（

考虑以下问题：

给定模板串集合 \(S\)，保证其中所有字符串的长度和不超过 \(L\)。对其建立广义 SAM，设其节点集合为 \(V\)，\(u \in V\) 所代表的字符串集合中最长的字符串为 \(longest_u\)，则考虑求出 \(\sum_{s \in S} \sum_{u \in V} [longest_u \subseteq s]\) 的渐进上界，其中两个字符串 \(s,t\) 满足 \(s \subseteq t\) 当且仅当 \(s\) 是 \(t\) 的子串。

在广义 SAM 的部分问题中可能会使用复杂度等于该值的算法：例如计算子串在多少个模板串中出现，可以建立广义 SAM 后对于每一个模板串找到其所有前缀在广义 SAM 上的节点，然后从它们开始暴力跳 parent 树算贡献，并给每个访问了的节点打上访问标记保证在同一个模板串的计算过程中一个点不经过两次。这个算法的复杂度上界就是上面问题提到的渐进上界。

给出结论：\(\sum_{s \in S} \sum_{u \in V} [longest_u \subseteq s] = O(L^{1.5})\)。

证明：分成两个部分，第一个部分证明渐进上界不高于 \(L^{1.5}\)，第二个部分构造一个渐进为 \(L^{1.5}\) 的模板串集合。

Part 1.

首先通过广义 SAM 的构造容易知道广义 SAM 的节点数是 \(O(L)\) 级别的。那么某个串 \(s \in S\) 在广义 SAM 上遍历的节点数不会超过 \(\min\{|s|^2 , L\}\)。接下来分两个情况考虑：

• 对于 \(|s| > L^{0.5}\) 的字符串，字符串数量不超过 \(L^{0.5}\)，节点数不超过 \(L^{1.5}\)；

• 对于 \(|s| < L^{0.5}\) 的字符串，由于 \(x^2\) 是下凸函数，因此遍历节点数在恰有 \(L^{0.5}\) 个长度为 \(L^{0.5}\) 的字符串上取到上界，否则可以通过调整得到更大的节点数。故上界为 \(L^{1.5}\)。

综上渐进上界不会超过 \(L^{1.5}\)。

Part 2.

构造实际上是简单的。构造一个长度约为 \((2L)^{0.5}\) 的随机字符串，然后 \(S\) 中包含其所有后缀即可。这样可以保证每个字符串的基本所有子串都会在广义 SAM 中。实测在 \(L = 45000,5 \times 10^5 , 2 \times 10^6\) 时该构造方式得到的遍历次数都可以达到 \(0.5L^{1.5}\) 左右。