Luogu6640 [BJOI2020] 封印

题意：给出两个字符串 。

多次询问 与 的最长公共子串长度。

允许离线，，时限 。

---

回忆「双串最长公共子串」。

先建立 的 SAM，用 在上面匹配，能得到 的每个前缀能匹配的后缀长度。

设前缀 在 中匹配长度为 ,即能匹配 。

整个 数组的 即为答案。

现在截取 的一个区间 ，那么 需要对 取 。

答案即为 。

考虑 取哪边，判别条件为 。

• 离线算法

  我们可以按照 的顺序回答询问，不断修改符合条件的 ，并查询区间最大值。这可以使用线段树维护。

• 在线算法

  发现 是单调不升的，因为 。

  所以满足条件的 一定是一段前缀，二分即可。

  需要 表来解决 。

复杂度均为 。