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

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

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

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

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

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

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

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

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

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

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

一、利用 SS 串 SAM 的 parent tree

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

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

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

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

二、利用 TT 串 SAM 的 parent tree

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

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

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

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

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

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

正解

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

由于限制条件是对于 SS 的,故只能在 SS 的 parent tree 作统计(参见上文方法一)。

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

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

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

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

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

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

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

(由于篇幅问题,给出云剪贴板链接。)

R78720367 记录详情 TT 的 parent tree 上遍历的解法

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

解法二

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

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

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

解法???

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

  • 2022年7月9日