P13531 [OOI 2023] A task for substrings / 字符串问题

JDScript0117 · 2026-01-22 18:25:59 · 题解

在省选模拟赛 T2 遇到了这道题，场上做出了一个复杂度为 O\left(|\Sigma| S + \sqrt[3]{(|t| + m)^{2} S m}\right) 的做法。赛后看了 solution 感觉十分高妙，但是我确实想不到把询问放到每个 s_{i} 上，于是决定记录一下场上的做法。

注意，这个只是一个不同的做法，不过它的复杂度比官方以及其它 solution 劣。

看到要求 f(t[l: r))，决定把它拆成 f(t[0: r)) + f(t[l: n)) - f(t:[0: n))。不过发现这个式子是错误的，它有一定可能会计算错 |s_{i}| > r - l 的 s_{i} 的贡献。不过容易发现那部分 s_{i} 的贡献应该为 0，于是想办法只计算 |s_{i}| \le r - l 的 s_{i} 的贡献。

第一反应是考虑增量的维护，即支持加入一个 s_{i}，求一个前/后缀的 f，经过一定思考发现这个不是很可做。

接下来考虑将 s_{i} 分块，在考场上想到了一个很神奇的分块方式，将 s 按长度排序，接下来令每一块的 \max\{|s_{i}|\} - \min\{|s_{i}|\} \le B。发现我们最多会分出来 \sqrt{\frac{S}{B}} 块。为了方便，我们之后将一块的 \min\{|s_{i}|\} 写作 mn，\max\{|s_{i}|\} 写作 mx。

对于一个 f(t[l: r))，我们知道算 |s_{i}| \le r - l 的串产生的贡献可以拆成前后缀全局加减（上文提到过）。于是对于 mx \le r - l 的块我们就可以这样算贡献。前后缀和全局的次数是可以使用 ACAM 计算的，复杂度是 O\left((|t| + m) \sqrt{\frac{S}{B}}\right) 的。

接下来我们就只需要考虑 mn \le r - l < mx 的块所产生的贡献了。我们想如果我直接将 t[l: r) 放 ACAM 里跑一边肯定是对的，但是时间复杂度是 O(\sum{r - l}) 的，肯定无法接受。再详细研究一下发现只有你的指针到了 [l + mn, r] 的位置才有可能对答案产生贡献。这一部分是可以暴力跑的，这是因为 r - l - mn < mx - mn \le B，所以时间复杂度是 O(m B) 的。

于是我们要考虑的问题就只有怎么求出在 ACAM 上跑了 t[l: l + mn] 后的节点位置。我们记录这个节点是 p_{l}，发现 p_{l} 就是 p_{l - 1} 在 ACAM 上往 t_{l + mn} 走后，一直跳 fail 直至深度不超过 mn 的节点。于是算一遍所有的 p_{l} 的位置就是 O(|t|) 的，对所有块算的复杂度就是 O\left(|t| \sqrt{\frac{S}{B}}\right) 的。

显然，对所有块建 ACAM 的复杂度是 O(|\Sigma| S)，因为所有的串都只会出现一次。

于是总复杂度就是 O\left(|\Sigma| S + m B + (|t| + m) \sqrt{\frac{S}{B}}\right)，B 取 O\left(\sqrt[3]{\frac{(|t| + m)^{2} S}{m^{2}}}\right) 时配平，最终复杂度就在开头。