洛谷题库 P4770 [NOI2018] 你的名字
本题考查对后缀数组或后缀自动机诸多性质综合、全面的应用,以及利用可持久化数据结构查询历史区间极值的方法。
也就是说,大体思路只花费一小时不到,去掉一个 log 却耗了我一天多……
“双指针”扫描求串 T 的每个前缀在 S 中匹配的最长子串
在任何时刻,SAM 的状态转移函数会将某字符串引向串 S 中的等价 endpos 状态。根据 endpos 和 parent tree 的性质,我们可以对前缀 T[1⋯k],k∈{1,2,⋯,∣T∣} 依次求出其最长的作为 S 的子串出现的后缀。
具体而言,假若我们知晓前缀 T[1⋯k] 的最长匹配后缀长 len,左端点 k−len+1,处在自动机状态 x。由于 len 是极大的,不可能在后续匹配中出现左端点 ≤k−len 的情况。考虑下一字符 T[k+1]=c。若存在转移 trans(x,c),则直接跳转到下一等价类,匹配长度自增 1;否则在该长度下失配,我们被迫右移左边界。不断令 x←link(x),len←maxlen(link(x)),也即调整到链接树的父亲状态的最大长度(根据定义,这显然是小于 len 的)。直至跳转到空串节点,或者存在上述转移位置。若存在转移则执行,匹配长度自增。
由于 len 在指针每右移一位最多自增 1;最多回跳 len 次,故而复杂度为 O(∣T∣)。
利用 SAM 求 T 有多少本质不同子串在 S 中出现的两种方法
这两种方法均与文本串长度无关或弱相关,也是为应对本题的特殊询问方式。
下文假设已经以 O(∣S∣) 的时间求出了 S 的 SAM。
一、利用 S 串 SAM 的 parent tree
通过上述方法,我们求出前缀 T[1⋯k] 的最长后缀匹配 L(T,k) 以及(在 S 的 parent tree 上)其所在节点 xk。
由于每个本质不同子串对应唯一 endpos,即对应唯一状态节点,那么实际上我们考虑了所有 parent tree 上根节点到 xk 的所有本质不同子串。因此若要去重,就要求取根节点到 xk,k∈[1,∣T∣] 的路径并上的长度之和。这是一个经典树上问题:我们按照 dfn 序对 x1,⋯,k 排序(其相对顺序显然无关紧要)。由于 parent tree 上父亲-儿子的最长匹配长度整数域上相邻,满足到根的路径上可加性,故似乎求取 ∑k=1∣T∣L(T,k)−∑k=2∣T∣maxlen(lca(xk−1,xk)) 就完成了。
存在一个问题:转移到 xk 仅代表 len∈(maxlen(link(xk)),maxlen(xk)],而非是该 endpos 的最大匹配长度。因此涉及到计算 lca 及其状态的最长匹配长度时,直接累加的结果不一定正确。最简单的处理方式是只考虑所有子树内不存在关键节点的节点,一来此节点子集的路径并与原来等价,二来可以保证减去的重复部分 maxlen(lca(xk−1,xk)) 可以安全无虞地取最大值,无需特殊处理。
由于涉及到 dfn 序、lca 的计算和利用数据结构(如树状数组)判断子树内是否存在关键点,时间复杂度为 O(∣T∣log∣S∣),常数略大。
二、利用 T 串 SAM 的 parent tree
我们还可以对 T 本身建立自动机——本来求的也是公共子串数,在 S 上统计和在 T 上计算是一样的。直接对其 SAM 的 parent tree 遍历一遍求路径并,可比笨拙的树上差分来得快多了。
具体而言,对于每个节点 y,我们知晓其等价类有 maxlen(y)−maxlen(link(y)) 个不同子串。故直接统计其子树内状态达到的最大匹配长度 len’y,取遍 [0,len’y]∩(maxlen(link(y)),maxlen(y)] 所有整数即可。
在求出各 L(T,k) 以后,我们找到 yk,即 T[1⋯k] 在 T 的自动机上对应的等价类状态,尝试更新最大匹配长度为 len’yk←k,遍历一遍 parent tree 即可。复杂度 O(∣T∣),常数较大。
68 pts 做法,L=1,R=∣S∣
根据题意,我们需要求 T 的所有本质不相同子串中,从未在 S 中出现过的数量。以全集减去补集:用 T 本质不同子串数量 减去 T,S 本质不同公共子串数量。
前者是后缀数组或者后缀自动机的经典应用。参见 P4070 [SDOI2016]生成魔咒。时间复杂度 O(∣T∣log∣T∣) 或者 O(∣T∣)。后者参见上文,不再赘述。总复杂度 O(∑∣T∣log∣S∣)。
正解
如果我们仍不加区分地,仍对 T 在完整的 S 的 SAM 作子串匹配,由于加上了询问区间 [L,R] 的限制,某个节点对答案贡献的正确性就有待商榷了。
由于限制条件是对于 S 的,故只能在 S 的 parent tree 作统计(参见上文方法一)。
仍考虑 parent tree 上 x 子树内的最大匹配长度 len’x。若该节点想要为答案作出贡献,则不仅要满足 len’x>maxlen(link(x)),还必须存在 l∈[L+maxlen(link(x)),R],l∈endpos(x)。(根据 endpos 的定义,如果某个位置 pos∈endpos(x),那么节点 x 的子树中必然存在 S[1⋯pos] 的等价类节点 y。)更通俗地说,有一个等价类里的字符串,它完整地包含于询问区间中: S[1⋯l] 的等价类节点 y 在 x 的子树中,且其右端点在 R 左侧,其截取 L 右侧的长度在 x 的等价类合法长度区间内。显然,对于同一个等价类,我们总是想要选择最大的不超过 R 的合法的 l,留给后缀的长度越大。
容易发现,随着在 parent tree 上节点的深度越来越浅,满足条件的 l 将越来越多,“该节点能否为一个长为 len’x 的后缀贡献答案”在深度上具有“0/1单调性”。故而若我们仍匹配出 T 的每一前缀在 S 整个串中出现的状态 xk,必须在其所有祖先中找到深度最大的合法节点。
经过我一个上午的研究,在 L,R,x 均作变量的情况下,该过程的复杂度下限为 O(log2∣S∣)。具体来讲,维护 parent tree 的 dfn 序列的可持久化线段树。我们按照 k=1,⋯,∣S∣ 的顺序,依次激活 S[1⋯k] 的等价类节点,将 dfn 序列上对应位置的最大值设置为 k。二分最大合法深度。对于某个节点 u,查询其子树对应 dfn 序区间在激活 k≤R 的节点时的区间最大值并判断,就达到了复杂度下限。(它是否存在对数时间解法?如果存在,请一定告诉我这个蒟蒻。不胜感激。
可是 ∑∣T∣≤106 啊。(我觉得请zjk帮忙卡常应该能过。只是我真的没胆去写这个解法。
然后在这里卡了 23 个小时。怎么办?
那我们就在匹配过程中做点文章吧。试想,假如 T 在自动机上的每一步匹配,都能够在保证等价类中存在满足条件的 l,使得某个子串完整包含于 [L,R] 的前提下,最大化匹配长度,不就一举解决了“完全不知从哪个深度才有合法长度的后缀字串”的问题么?!这样一来,令 L’(T,k) 为在该条件下的最大匹配,x’k 为该等价类对应节点,直接套用 L=1,R=∣S∣ 的部分分解法即可。
参见文章开头的匹配方法。仍旧考虑匹配到 T[1⋯k],最大后缀长 len,当前处于状态 x。则匹配时的转移有一个更强的限制:trans(x,c) 的子树中,存在合法 l 的等价类。判定方法与上文中提到的可持久化线段树查询“依次激活的节点序列”的历史区间最值一样:trans(x,c) 子树的 dfn 序列区间中,找到激活 R+1 之前的最大的元素 l,考虑是否有 l−L+1>maxlen(link(trans(x,c))),若是则执行转移。通过归纳法和 len 极大的性质,可以轻松说明该算法的正确性。
复杂度的分析同理:回跳至多造成 O(lenlog∣S∣) 的查询开销,故总复杂度 O(∣T∣log∣S∣) 常数略大。之后施行相仿的路径求并,或者在 T 上的自动机求解,都是安全无虞的。总时间复杂度 O(∣S∣+∑∣T∣log∣S∣) 或 O(∣S∣+∑∣T∣)。
(由于篇幅问题,给出云剪贴板链接。)
R78720367 记录详情 在 T 的 parent tree 上遍历的解法
R78735760 记录详情 在 S 的 parent tree 上求路径并并使用 SA 求出本质不同子串数的解法
解法二
通过 SA 与主席树的方式一样可以解决本题。
简单来说,仍然利用了双指针匹配极大子串的线性复杂度的性质,同时在 rank 相邻的一个区间中求出满足被 [L,R] 的最长转移。复杂度是超大常数的 O((∣S∣+∑∣T∣)log(∣S∣+∑∣T∣))。
洛谷题解讲的还不错。我就不写了。
解法???
根据部分分解法的思想在 parent tree 上暴跳。可以通过 CCF 官方数据,但过不了 @Wen_kr 的 hack 数据。