某岛

… : "…アッカリ~ン . .. . " .. .
July 12, 2021

UOJ #608. 【UR #20】机器蚤分组

题意

https://uoj.ac/problem/608
给定一个字符串 T,每次询问一个子串 T[l,r],返回其最长重复子串的长度。

做法

证明?参考 官方题解
我们来讨论怎么用 SAM 搞子串的重复子串。

首先回忆怎么用 SAM 求最长重复子串。
直接返回 fail 树上非叶子节点的 len[u] 就好。

再考虑怎么求某个前缀 T[1,r] 的最长重复子串。
我们考虑离线,按照 r 端点从小到大排序,
按照顺序每次在 fail 树上找到前缀所对应的叶子节点,
往根节点染色即可。用染色路径上第一个碰到的节点的 len 的长度更新答案。
因为每个节点只会被染色一次,所以暴力染色即可。

最后考虑一般情况 T[l,r],我们显然需要对染色进行区分,
我们希望每个状态越晚被染色越好,因为越晚,它可能对答案的贡献就越长。
我们不妨画一下示意图。。考虑下面的情况。。考虑到时刻 r 的时候经过节点 u。
u 历史上在时点 l1 和 l2 都被染色过,且 len[u] = 4,那么有:
设 l1 < l2 < r。
—l1, —l2, —r
那么我们可以忽略 l1,并且只有在 l <= l2-3 的时候,才能得到
完整的 4 长度的贡献,在 l2 时刻,因为询问的左区间不够长,只有对答案带来 1 的贡献。

具体说来,不妨对每个可能三元组 (l,r,u)。
r 表示当前染色的时点,l 表示历史上这个节点最晚被染色的时点。
u 表示 l, r 到根路径上的某个公共祖先。

我们可以用线段树。。。
支持询问区间最值,
以及区间覆盖,和区间等差数列覆盖两个操作即可。

具体说来就是。。。
checkMax1(1, l-len[u], len[u]),表示对区间 [1, 1-len[u]] 与 len[u] 取 max。
以及
checkMax2(l-len[u]+1, l),表示对 l-len[u]+1, l-len[u]+2,…, l 这个区间分别 checkMax 上 l, l-1, …, 1 这个递减数列。

因为染色过程总是叶子到根节点的路径,所以可以用动态树。
这里的动态树也可以用启发式合并替代。