后缀自动机练习笔记

打完NOI以后发现Day1T3的68分掉了很亏,突然发现只会hash也做不出什么难一点的题目了,所以需要重新好好地学习一下一些复杂一点的字符串算法了


SAM

学习资料:
APIO2018后缀自动机器PPT的HTML版本:后缀自动机学习笔记


基本应用

LCS

对A建立SAM,B在SAM上面跑,如果有trans就跳,长度+1,如果没有则跳parent,答案对长度取$max$

多串LCS

对第一个字符串建立SAM,对多个串匹配,保留SAM上每个结点的答案最小值,然后取max。对于状态$p$,在SAM中如果可以找到匹配,那么他的父亲也同样可以找到匹配,所以对SAM拓扑排序以后倒序更新即可。

本质不同子串计数

根据SAM三分率,对于任意$u,v$,其所包含的子串是没有交的。答案就是$mxl[u]-mnl[u]+1$,然而根据性质,$mnl[u]=mxl[parent[u]]+1$,所以答案就是$\sum_{i}^{cnt} mxl[i]-mxl[par[i]]$

长度为K的子串中出现次数最多的子串的出现次数

比较简单,在SAM上Toposort以后求出size,对于状态$u$,用$size[u]$去更新$ans[mxl[u]]$即可。

多个数字串本质不同的子串组成的数字求和

如果要处理单串,可以从Topo序从前向后递推,$sum[trans[u][c]]=sum[u] \times 10+ c \times size[u]$。对于多个串,一个常用的方法是在串与串之间加入”#”或其他符号,跑一次SAM。设状态$u$包含的没有”#”的子串的个数为$usedablesize$。答案为$sum[trans[u][c]]=sum[u] \times 10+ c \times useablesize[u]$。这个$usedablesize$的求法也是递推,$usedablesize[1]=1$,如果有转移边,直接相加即可。


练习题

BZOJ3998 弦论

对于$T = 0$的情况,SAM上的每一个节点代表一个串。对于$T=1$的情况,对于一个节点出现的次数就是$|endpos|$。找第$K$大的方法与在平衡树里面找$K$大的方法类似,维护一个子树之和,从上往下找即可。

BZOJ2946 公共串

同LCS2,简要代码如下

BZOJ3926 诸神眷顾的幻想乡

首先题目中的信息告诉我们只有20个叶节点,如果可以把所有串建立到SAM上,串的总数是$\log n$级别的。多个串的匹配需要用到广义后缀自动机,可以在后缀自动机里面插入一棵Trie树,具体做法是每次插入节点的时候把SAM的last指针移到它在Trie树上面的父亲所对应的SAM结点上,然后照常插入。加一个特判,如果当前结点的子树里面有需要的节点,则不需要开新的节点。对于本题,只需要插入20次,然后求出本质不同的字符串个数即可。

BZOJ2882 工艺

求最小表示法,但是字符集无限大。对于有限的字符集,方法是把串复制一遍插入SAM,然后从SAM的Root开始,每次走最小的结点,走$n$步就能得到答案。对于无限大的字符集,就利用$std::map$代替转移数组即可。(比AC自动机的map版好打多了。

BZOJ 3238 差异

把读入的字符串反过来建立$SAM$。对应的$parent$树就是对于这个串正序后缀树,一个结点就代表一个后缀。
$$
\sum_{1 \le i < j \le n}{len(T_i) + len(T_j) – lcp(T_i,T_j)}
$$
我们发现$\sum_{1 \le i < j \le n}{len(T_i) + len(T_j)}$是可以直接算的。
它等于$\sum i \cdot (n-1) = n \cdot (n-1) \cdot (n-2) / 2$。
而后面的$lcp$转化为后缀树上面的LCA,$\sum lcp$可以树形DP求,设$f_i$表示$i$点为$LCA$时的$lcp$之和。那么$f_i=C(size[i],2) \cdot lcp$,这个$lcp$就是此时在后缀树上的深度,也就是$LCA$的$maxl$。
然而求的时候可以把深度分层(不然会算重复),也就是计算的时候把一个点对答案的贡献当成只有在比父亲结点深度大,比自己小的那一段上。最后计算答案的时候也就是$f_i=C(size[i],2) \cdot (mxl[i]-mxl[par[i]])$。

BZOJ 2754 喵星人的点名

留了多年的坑..没想到SAM也可以写。
对于姓名建立广义SAM,每次询问的时候在SAM上面跑。建立SAM的时候:
(1)转移边要用std::map
(2)每次插入一个点的时候类似AC自动机,把它parent树上的所有点更新一遍,但是要注意重复
(3)SAM新建nq的时候需要复制q的所有信息,包括SAM维护的其他信息

对于操作一,维护一个cnt,对于询问跑的时候输出对应点的$cnt$。
对于操作二,用vector维护这个点包含哪些名字,同上输出
然后 BZOJ AC, Luogu TLE
其实这个东西是假的,在第二问的复杂度高达$O(nm)$
代码:Link
改进第二问,方法是每次匹配询问以后在匹配点+1,然后遍历给出的名字。对于每一个字符,暴力跳parent然后计算和,同样的需要注意重复。
这个做法复杂度期望$O(n\sqrt n) $,因为$parent$树的深度期望是根号级别的。
代码:Link

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

*