UOJ #608. 【UR #20】机器蚤分组
source link: http://www.shuizilong.com/house/archives/uoj-608-%e3%80%90ur-20%e3%80%91%e6%9c%ba%e5%99%a8%e8%9a%a4%e5%88%86%e7%bb%84/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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 这个递减数列。
因为染色过程总是叶子到根节点的路径，所以可以用动态树。
这里的动态树也可以用启发式合并替代。
Posted by
xiaodao
Category: 日常
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK