Luogu5576 [CmdOI2019] 口头禅

发表于 分类于 ， ， 阅读次数：

题意：给出 个字符串 。

共有 次询问，每次给出 求字符串 的最长公共子串长度。

，，，时限 ，空限 。

本题的 SAM 上两个自然根号做法，以及一个 polylog 做法。

算法一：分治

  • 前置知识：用 SAM 求 个字符串的 LCS。

    任取一个字符串 作为基准匹配串，剩下的是文本串。

    对于其中一个文本串 ，令 表示 中 在 中出现过，即以 结尾的位置的最长匹配长度。

    这是经典问题，用 在 的 SAM 中匹配一次即可求得，故不赘述。

    最后将所有匹配串所得到的 取 ，最后把整个数组取 即可。

    记串长总和为 ，建 SAM 的复杂度为 ， 要在每个 SAM 上跑匹配，复杂度 。总复杂度为

    很明显，选择这些字符串中长度最短的串做基准串，跑的最快。

没有强制在线，考虑猫树分治。

注：把分治树存下来，类似于猫树就可以做到强制在线。但所需空间较大，并不实用。

分治到某个区间 时，选取关键串 。处理所有跨越 的询问。

以 为基准匹配串，分别向左向右匹配，求出各个 数组的“前缀 ”。求答案时，将询问区间的两个端点处的 前缀 合并，然后对整个数组取 即可。

若分治时选择的 较长，则复杂度会退化，故直接使用取中点的普通分治是不可行的。考虑设计更好的分治策略：倍增分治。

  • 对于阈值 ，称长度小于等于 的为短串，长度大于 的为长串。记总串长为 ，显然长串的个数为 。

  • 分治到某区间之后，找出所有短串，取其中间位置做基准串。这样分治直到区间里都是长串，将阈值 增加 。

接下来计算该算法的复杂度。

  • 求

    观察分治树，对于一个 ，对应的短串在 层分治后就被耗尽。

    阈值为 时，分治区间的总大小是 的，基准匹配串的长度为 ，故花费的时间为 。

    阈值 共有 个，故总复杂度为 。

  • 处理询问

    分治中，合并答案的复杂度为 对应基准串长度。

    观察上面的分治，不难发现，一个询问区间所对应的基准串，不会超过区间中最短串的 倍。

    这里会产生一个自然根号。对询问记忆化后，复杂度为 。证明如下：

    • 结论：数列 和为 ，询问 的代价是 。记忆化后， 次询问的代价不超过 。

    该结论可以加强为

    • 结论：数列 和为 ，询问 的代价是 。记忆化后， 次询问的代价不超过 。

      证明：设定阈值 ，称大于 的元素为大元素，否则为小元素。大元素不超过 个。

      • 若 之一是小元素，询问代价不超过 。

      • 若代价大于 ， 必须都是大元素，这些询问的代价总和是

      总复杂度 ，令 得最优复杂度 。

综上所述，时间复杂度为 ，空间复杂度线性。

所有操作均为暴力 for 和取 ，常数较小，可以轻松通过本题。

利用 数组也可求出区间本质不同公共子串数目。留做习题。

算法二：广义 SAM + 扫描线

对于广义 SAM 上的节点 ，记 为在 parent 树中 子树内存在终止节点的串的集合。

当询问区间 时，若 ，则点 可以向答案贡献。

序列扫描线。考虑逐步增大 ，维护每个 的答案。

对于 SAM 上的点 ，记 中从 向前的极长连续段的左端点为 。

在询问 时，若 则点 能贡献。

这里又有一个自然根号：广义 SAM 上 是 级别的。

于是，在 增加时，对所有 中含 的点暴力更新即可。

有 次单点修改， 次区间查 ，使用 分块，复杂度为 。

卡常后可以通过本题。

算法三：广义 SAM + 线段树

可见 （Mina）【题解】[CmdOI2019] 口头禅 广义 SAM -永无岛

这里也简要地介绍一下该做法。

用 std::set 维护 中的连续段，然后启发式合并。这部分复杂度为 。

按照节点的 从大到小枚举，由于 parent 树上 从深到浅递减，故按这个顺序也可以顺便进行合并。

每次合并后，若产生新的连续段（该事件最多会发生 次），回答所有当前节点能够贡献到的询问，然后将这些询问删除。

使用线段树维护询问，将询问 挂在位置 ，权值为 。

需要寻找 包含的所有询问时，查询 内的权值最小值 ，若 ，则说明找到了一个合适的区间。

复杂度为 ，空间也是线性。