题意 https://uoj.ac/problem/608 给定一个字符串 T，每次询问一个子串 T[l,r]，返回其最长重复子串的长度。 做法 证明？参考 官方题解。 我们来讨论怎么用 SAM 搞子串的重复子串。 首先回忆怎么用 SAM 求最长重复子串。 直接返回 fail 树上非叶子节点的 len[u] 就好。 再考虑怎么求某个前缀 T[1,r] 的最长重复子串。 我们考虑离线，按照 r 端点…
题意 https://uoj.ac/problem/608 给定一个字符串 T，每次询问一个子串 T[l,r]，返回其最长重复子串的长度。 做法 证明？参考 官方题解。 我们来讨论怎么用 SAM 搞子串的重复子串。 首先回忆怎么用 SAM 求最长重复子串。 直接返回 fail 树上非叶子节点的 len[u] 就好。 再考虑怎么求某个前缀 T[1,r] 的最长重复子串。 我们考虑离线，按照 r 端点…
讨论
登录后参与讨论
还没有评论，来说第一句吧。