题解 P4070 【[SDOI2016]生成魔咒】

hehelego · 2019-03-05 16:55:03 · 题解

前面已经又两三个题解提到了使用SAM的玩法了, 具体而言就是一句话.

考虑新建的后缀状态是q
经过神奇的分类讨论论证,各种parent树上操作,产生了状态分裂,修改了trans的指向,修正了parent之后.
贡献是\text{maxlen}_q-\text{maxlen}_{\text{parent}(q)}.

这里给出一个看起来比较有说服力的正确性证明.

首先,我们先来考虑 S的本质不同的子串 如何统计.
直接考虑扔上\text{SAM}(S),把子串T扔到里面去,由于是子串\text{tr}(q_s,T)=q_0\neq \text{null}
如果两个子串T_1,T_2是本子不同的,即T_1\neq T_2,那我们一定有 \text{len}(T_1)\neq \text{len}(T_2) 或 \text{tr}(q_s,T_1)\neq \text{tr}(q_s,T_2),
若不然,经过长度相等的路径,到达相同的状态,设q_0=\text{tr}(q_s,T_1),在q_0状态的right集合中随便取出一个元素r,有T_1\!=\!T_2=S[r-\text{len}+1,r]
写出这个只是搬运了定义的式子,仍然不知道它是什么意思? 我这里给出一个解释,考虑一个长度确定为|T|的子串,如果我们知道一个x\in right(T), 那么取出"以位置x结尾,长度为|T|的串S[x-|T|+1,x]",它一定等于T. 这里T_1,T_2长度一致, 又有一样的\text{right}集合, 随便从right中找一个元素, 向前取 T_1 个字符, 得到子串T_0, 就有T_1=T_0=T_2.

这说明 \text{SAM}(S)中, q_s起始的不同路径和S的本质不同子串 一一对应 这个性质非常重要,在\text{kth}(T),\text{rank}(T)(指字典序)相关的问题中有很多应用.

然后来考虑怎么数路径,SAM上面的性质是"两条路径要么终点不同,要么长度不同",我们可以枚举终点状态,然后考虑到达此状态的路径,其长度有多少种可能.
比如考虑走到q的子串,我们发现到达状态q的所有路径长度形成一个连续区间.

所有走到q的子串,其\text{right}集合是相同的,从R_q中任意取出一个位置r,
考察S[r,r],S[r-1,r],S[r-2,r], \ldots S[1,r]
会发现\text{right}(S[r,r])\supset \text{right}(S[r-1,r])\supset \text{right}(S[r-2,r])\supset \ldots \text{right}(S[1,r])
(简单来说,就是长度越短,越容易多次出现. 如果r'\in \text{right}(S[r-i,r])那么r'\in \text{right}(S[r-i+1,r]),因为后者是前者的后缀).
如果存在到达q,长度为i的路径与长度为j的路径,其中i<j,会有\text{right}(S[r-j+1,r])=\text{right}(S[r-i+1,r])按照前面的单调性关系,以j结尾长度为i+1,i+2\ldots j-1的子串,right会和它们一样,这些子串也应当对应一些SAM上从q_s走到q的路径,其长度覆盖了[i+1,j-1].

于是, 答案就写成这样, 其中[\text{maxlen}_{\text{parent}(q)}+1,\text{maxlen}_q]就是那个长度区间.

然后我们再来考虑插入字符,从\text{SAM}(S)到\text{SAM}(Sc)时发生的变化.直观的说,新增加的(在S中不出现的)子串,都是以n+1结尾的.形式化的讲,他们都对应于\text{tr}(q_s,T)=\text{nq}的T,这里需要先考虑一个性质
(原谅我不能说明白为啥要考虑这个性质...只能说这个性质是在考虑SAM中加字符时状态的\text{right}改变时需要用的...可以说你不仔细看SAM的理论直接被板子是肯定不知道的)

如果两个串T_1,T_2,在S中,\text{right}(T_1)\neq \text{right}(T_2)那么Sc中就不会有\text{right}(T_1)=\text{right}(T_2),这个东西只能正向推,反向是不正确的.这个性质说明,添加字符,不会导致SAM上的状态合并,回顾:状态是\text{right}等价类.

然后有什么帮助呢? 这个性质说明, 新增贡献在且仅在在\text{nq}上面.

其他状态统计到的子串总和会是S中本质不同的子串,Sc中仍然是本质不同的.