洛谷题库 P4770 [NOI2018] 你的名字 题解与思路重现

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

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

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

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

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

具体而言，假若我们知晓前缀 $T[1\cdots k]$ 的最长匹配后缀长 $\mathrm{len}$，左端点 $k-\mathrm{len}+1$，处在自动机状态 $x$。由于 $\mathrm{len}$ 是极大的，不可能在后续匹配中出现左端点 $\leq k-\mathrm{len}$ 的情况。考虑下一字符 $T[k+1]=c$。若存在转移 $\operatorname{trans}(x,c)$，则直接跳转到下一等价类，匹配长度自增 $1$；否则在该长度下失配，我们被迫右移左边界。不断令 $x \leftarrow \operatorname{link}(x),\mathrm{len}\leftarrow \operatorname{maxlen}(\operatorname{link}(x))$，也即调整到链接树的父亲状态的最大长度（根据定义，这显然是小于 $\mathrm{len}$ 的）。直至跳转到空串节点，或者存在上述转移位置。若存在转移则执行，匹配长度自增。

由于 $\mathrm{len}$ 在指针每右移一位最多自增 $1$；最多回跳 $\mathrm{len}$ 次，故而复杂度为 $\mathrm{O}(|T|)$。

利用 SAM 求 $T$ 有多少本质不同子串在 $S$ 中出现的两种方法

这两种方法均与文本串长度无关或弱相关，也是为应对本题的特殊询问方式。

下文假设已经以 $\mathrm{O}(|S|)$ 的时间求出了 $S$ 的 SAM。

一、利用 $S$ 串 SAM 的 parent tree

通过上述方法，我们求出前缀 $T[1\cdots k]$ 的最长后缀匹配 $\operatorname{L}(T,k)$ 以及（在 $S$ 的 parent tree 上）其所在节点 $x_k$。

由于每个本质不同子串对应唯一 $\mathrm{endpos}$，即对应唯一状态节点，那么实际上我们考虑了所有 parent tree 上根节点到 $x_k$ 的所有本质不同子串。因此若要去重，就要求取根节点到 $x_k, k \in [1, |T|]$ 的路径并上的长度之和。这是一个经典树上问题：我们按照 $\mathrm{dfn}$ 序对 $x_{1,\cdots,k}$ 排序（其相对顺序显然无关紧要）。由于 parent tree 上父亲-儿子的最长匹配长度整数域上相邻，满足到根的路径上可加性，故似乎求取 $\sum_{k=1}^{|T|}\operatorname{L}(T,k)-\sum_{k=2}^{|T|}\operatorname{maxlen}(\operatorname{lca}(x_{k-1},x_k))$ 就完成了。

存在一个问题：转移到 $x_k$ 仅代表 $\mathrm{len}\in (\operatorname{maxlen}(\operatorname{link}(x_k)),\operatorname{maxlen}(x_k)]$，而非是该 $\mathrm{endpos}$ 的最大匹配长度。因此涉及到计算 $\operatorname{lca}$ 及其状态的最长匹配长度时，直接累加的结果不一定正确。最简单的处理方式是只考虑所有子树内不存在关键节点的节点，一来此节点子集的路径并与原来等价，二来可以保证减去的重复部分 $\operatorname{maxlen}(\operatorname{lca}(x_{k-1},x_k))$ 可以安全无虞地取最大值，无需特殊处理。

由于涉及到 $\mathrm{dfn}$ 序、$\operatorname{lca}$ 的计算和利用数据结构（如树状数组）判断子树内是否存在关键点，时间复杂度为 $\mathrm{O}(|T| \log |S|)$，常数略大。

二、利用 $T$ 串 SAM 的 parent tree

我们还可以对 $T$ 本身建立自动机——本来求的也是公共子串数，在 $S$ 上统计和在 $T$ 上计算是一样的。直接对其 SAM 的 parent tree 遍历一遍求路径并，可比笨拙的树上差分来得快多了。

具体而言，对于每个节点 $y$，我们知晓其等价类有 $\operatorname{maxlen}(y)-\operatorname{maxlen}(\operatorname{link}(y))$ 个不同子串。故直接统计其子树内状态达到的最大匹配长度 $\mathrm{len}’_y$，取遍 $[0, \mathrm{len}’_y] \cap (\operatorname{maxlen}(\operatorname{link}(y)),\operatorname{maxlen}(y)]$ 所有整数即可。

在求出各 $\operatorname{L}(T,k)$ 以后，我们找到 $y_k$，即 $T[1\cdots k]$ 在 $T$ 的自动机上对应的等价类状态，尝试更新最大匹配长度为 $\mathrm{len}’_{y_{k}}\leftarrow k$，遍历一遍 parent tree 即可。复杂度 $\mathrm{O}(|T|)$，常数较大。

$\textbf{68 pts}$ 做法，$L=1, R=|S|$

根据题意，我们需要求 $T$ 的所有本质不相同子串中，从未在 $S$ 中出现过的数量。以全集减去补集：用 $T$ 本质不同子串数量 减去 $T, S$ 本质不同公共子串数量。

前者是后缀数组或者后缀自动机的经典应用。参见 P4070 [SDOI2016]生成魔咒。时间复杂度 $\mathrm{O}(|T| \log |T|)$ 或者 $\mathrm{O}(|T|)$。后者参见上文，不再赘述。总复杂度 $\mathrm{O}(\sum |T|\log |S|)$。

正解

如果我们仍不加区分地，仍对 $T$ 在完整的 $S$ 的 SAM 作子串匹配，由于加上了询问区间 $[L,R]$ 的限制，某个节点对答案贡献的正确性就有待商榷了。

由于限制条件是对于 $S$ 的，故只能在 $S$ 的 parent tree 作统计（参见上文方法一）。

仍考虑 parent tree 上 $x$ 子树内的最大匹配长度 $\mathrm{len}’_x$。若该节点想要为答案作出贡献，则不仅要满足 $\operatorname{len}’_x>\operatorname{maxlen}(\operatorname{link}(x))$，还必须存在 $l \in [L+\operatorname{maxlen}(\operatorname{link}(x)),R], l \in \operatorname{endpos}(x)$。（根据 $\mathrm{endpos}$ 的定义，如果某个位置 $\mathrm{pos} \in \mathrm{endpos}(x)$，那么节点 $x$ 的子树中必然存在 $S[1\cdots \mathrm{pos}]$ 的等价类节点 $y$。）更通俗地说，有一个等价类里的字符串，它完整地包含于询问区间中： $S[1\cdots l]$ 的等价类节点 $y$ 在 $x$ 的子树中，且其右端点在 $R$ 左侧，其截取 $L$ 右侧的长度在 $x$ 的等价类合法长度区间内。显然，对于同一个等价类，我们总是想要选择最大的不超过 $R$ 的合法的 $l$，留给后缀的长度越大。

容易发现，随着在 parent tree 上节点的深度越来越浅，满足条件的 $l$ 将越来越多，“该节点能否为一个长为 $\mathrm{len}’_x$ 的后缀贡献答案”在深度上具有“0/1单调性”。故而若我们仍匹配出 $T$ 的每一前缀在 $S$ 整个串中出现的状态 $x_k$，必须在其所有祖先中找到深度最大的合法节点。

经过我一个上午的研究，在 $L, R, x$ 均作变量的情况下，该过程的复杂度下限为 $\mathrm{O}(\log^2 |S|)$。具体来讲，维护 parent tree 的 $\mathrm{dfn}$ 序列的可持久化线段树。我们按照 $k=1, \cdots, |S|$ 的顺序，依次激活 $S[1\cdots k]$ 的等价类节点，将 $\mathrm{dfn}$ 序列上对应位置的最大值设置为 $k$。二分最大合法深度。对于某个节点 $u$，查询其子树对应 $\mathrm{dfn}$ 序区间在激活 $k \leq R$ 的节点时的区间最大值并判断，就达到了复杂度下限。（它是否存在对数时间解法？如果存在，请一定告诉我这个蒟蒻。不胜感激。

可是 $\sum |T| \leq 10^6$ 啊。（我觉得请zjk帮忙卡常应该能过。只是我真的没胆去写这个解法。 然后在这里卡了 $23$ 个小时。怎么办？

那我们就在匹配过程中做点文章吧。试想，假如 $T$ 在自动机上的每一步匹配，都能够在保证等价类中存在满足条件的 $l$，使得某个子串完整包含于 $[L, R]$ 的前提下，最大化匹配长度，不就一举解决了“完全不知从哪个深度才有合法长度的后缀字串”的问题么？！这样一来，令 $\operatorname{L’}(T, k)$ 为在该条件下的最大匹配，$x’_k$ 为该等价类对应节点，直接套用 $L=1,R=|S|$ 的部分分解法即可。

参见文章开头的匹配方法。仍旧考虑匹配到 $T[1\cdots k]$，最大后缀长 $\mathrm{len}$，当前处于状态 $x$。则匹配时的转移有一个更强的限制：$\operatorname{trans}(x,c)$ 的子树中，存在合法 $l$ 的等价类。判定方法与上文中提到的可持久化线段树查询“依次激活的节点序列”的历史区间最值一样：$\operatorname{trans}(x,c)$ 子树的 $\mathrm{dfn}$ 序列区间中，找到激活 $R+1$ 之前的最大的元素 $l$，考虑是否有 $l-L+1>\operatorname{maxlen}(\operatorname{link}(\operatorname{trans}(x,c)))$，若是则执行转移。通过归纳法和 $\mathrm{len}$ 极大的性质，可以轻松说明该算法的正确性。

复杂度的分析同理：回跳至多造成 $\mathrm{O}(\mathrm{len} \log |S|)$ 的查询开销，故总复杂度 $\mathrm{O}(|T| \log |S|)$ 常数略大。之后施行相仿的路径求并，或者在 $T$ 上的自动机求解，都是安全无虞的。总时间复杂度 $\mathrm{O}(|S|+\sum|T|\log |S|)$ 或 $\mathrm{O}(|S|+\sum|T|)$。

（由于篇幅问题，给出云剪贴板链接。）

R78720367 记录详情 在 $T$ 的 parent tree 上遍历的解法

R78735760 记录详情 在 $S$ 的 parent tree 上求路径并并使用 SA 求出本质不同子串数的解法

解法二

通过 SA 与主席树的方式一样可以解决本题。

简单来说，仍然利用了双指针匹配极大子串的线性复杂度的性质，同时在 $\mathrm{rank}$ 相邻的一个区间中求出满足被 $[L, R]$ 的最长转移。复杂度是超大常数的 $\mathrm{O}((|S|+\sum |T|)\log (|S|+\sum |T|))$。

洛谷题解讲的还不错。我就不写了。

解法？？？

根据部分分解法的思想在 parent tree 上暴跳。可以通过 CCF 官方数据，但过不了 @Wen_kr 的 hack 数据。