Luogu4770 [NOI2018] 你的名字

题意：给出文本串 。

次询问，每次给出串 与区间 ，求 的不在 中出现过的本质不同子串数目。

，，。时限 ，空限 。

---

套路题。

单组询问

记 表示 在 中匹配的最长后缀长度。

这是一个经典问题，可以使用双指针求解：

• 类似 AC 自动机，要添加字符时，若当前节点无出边，则跳父亲，直到有出边为止。

求出 数组后，对 建立 SAM。

对于某个 SAM 节点，记串长区间为 ，endpos 集合为 ，则找出任意一个 ，该节点中不在 中出现的串的个数为 。

---

区间询问

仍考虑求出 数组。

观察我们在双指针算法中做了什么：

• 查看是否存在出边

• 跳父亲

在 的 SAM 上用线段树合并维护 endpos。

查看字符 的出边时，记当前的匹配长度为 ，当前节点为 。

找出 ，查看 中是否存在 。

若满足条件，则 ，且 加一。

若 不存在或不符合条件，则 减一，若 不在 的串长区间内则跳父亲。

复杂度 。