可持久化线段树

洛谷题库 P4770 [NOI2018] 你的名字

本题考查对后缀数组或后缀自动机诸多性质综合、全面的应用，以及利用可持久化数据结构查询历史区间极值的方法。

也就是说，大体思路只花费一小时不到，去掉一个 $\log$ 却耗了我一天多……

“双指针”扫描求串 $T$ 的每个前缀在 $S$ 中匹配的最长子串

在任何时刻，SAM 的状态转移函数会将某字符串引向串 $S$ 中的等价 $\mathrm{endpos}$ 状态。根据 $\mathrm{endpos}$ 和 parent tree 的性质，我们可以对前缀 $T[1\cdots k], k \in \{1, 2,\cdots, |T|\}$ 依次求出其最长的作为 $S$ 的子串出现的后缀。 （更多…）