[Str记录]CF204E Little Elephant and Strings

· · 个人记录

题意 ：

给出含有 n 个字符串的数组 A ，称第 i 个字符串为 A_i

对于每个 A_i ,求满足如下条件的二元有序対 (l,r) 的个数 ：

------------ 对所有串建立广义 $\rm SAM$。 首先对于每个节点点求出子树内串的种类数。 - 方法① ： 线段树合并 求并集大小的经典方法，时空复杂度均为 $O(n\log n)$。 - 方法② ： 大力跳 $\rm parent\ tree

对于每个节点，记录上一次是被那个串覆盖。从每个串的各个前缀向上跳，若已被此串标记，则停止。

复杂度是 O(n\sqrt{n}) 的，证明如下 ：

设所有串的总长为 n。

对于某个串 S ，其贡献的复杂度为 O\big(\min(|S|^2,n)\big)。

当 |S|>\sqrt{n} 时，这样的串只有 O(\sqrt{n}) 个，就算跑满 O(n) 的复杂度，也仅为 O(n\sqrt{n})。

当 |S|\leq \sqrt{n} 时，复杂度不超过 O(\sum |S|^2)\leq O(n*\max|S|)=O(n\sqrt{n})。

对于串 A_i，对每个 l 考虑能够贡献的 A_i[l,r] 个数。

可以从代表后缀 l 的点向上跳，直到串的种类数达到 k 为止。

此时到达节点的 len 即为 A_i[l,r] 的长度上界,也就是贡献。

可以不向上跳，而把合法的长度推向子树。

下面给出 O(n\sqrt{n}) 的实现。