前置芝士

后缀数组SA

后缀自动机SAM与广义后缀自动机(广义SAM)

这里面有很多题SA和SAM都可以做，如果有多做法我会简单提一句

后缀数组SA

P4248 [AHOI2013]差异

首先把加减与乘积拆开

前一部分的答案为 \((n-1)\sum\limits_{i=1}^n i=\dfrac{n(n-1)(n+1)}{2}\)

后面就是求LCP之和

注意到LCP是height之间最小的那一个，可以单调栈找出以\(height_i​\)为\(\min​\)的范围即可

SA求出height即可

SAM做法

前面都是一样的，后面求出子树中节点个数乘一乘即可

P1117 [NOI2016] 优秀的拆分

考虑求出以\(i\)为结尾的\(AA\)数量\(f_i\)与以\(i\)为开头的\(BB\)数量\(g_i\)

答案即为

\(f\)的求法与\(g\)类似，这里只考虑求出\(g\)

枚举\(A\)的长度\(len\)，每隔\(len\)标记一个关键点，那么一个长度为\(2len\)的\(BB\)一定会覆盖两个关键点。

设两个关键点为\(i,j(i<j)\)，那么\(i,j\)在一对\(AA\)里的条件是\(LCS(i,j)+LCP(i,j)\ge len\)

设重叠部分长度为\(x=LCS(i,j)+LCP(i,j)-len\)

那么对于\([i-LCP(i,j)+1,i-LCP(i,j)+1+x]\)内的点，g都需要\(+1\)

区间加用差分，LCP，LCS用后缀数组求出

SAM做法

基本一致，只是LCP和LCS用SAM求

P2178 [NOI2015] 品酒大会

与P4248 [AHOI2013]差异类似，单调栈，顺便维护最大值次大值，最小值次小值即可

SAM做法

与P4248 [AHOI2013]差异类似，维护子树中最大值次大值，最小值次小值

bzoj4278. [ONTAK2015]Tasowanie

将两个串拼起来，中间加个\(inf\)，按照rk贪心选择即可

原理就是如果当前位不同，肯定贪心地选小的。否则要依次比较后面哪个能更快选到更小的

后缀自动机SAM

loj6401. yww 与字符串

建出后缀自动机，求出每个节点能向前延伸的最长距离

parent树上DFS，当前节点能延伸的最长长度为\(\min(\max\limits_{v\in subtree_u}val[v],len[u])\)

对答案的贡献为\(max(0, min(len[u], mx[u]) - len[fa[u]])\)

原理就是求用SAM求不同子串数的那个结论

SA做法

参见官方题解

loj6041. 「雅礼集训 2017 Day7」事情的相似度

对于一个节点，对应一个endpos集合，这个endpos集合的LCS至少是\(len[u]\)，也就是我们现在有若干修改，形如\((x,y,z)\)，表示\(x,y\)之间的LCS为\(z\)

询问就是求\(x\ge l,y\le r\)的修改中，\(z\)的最大值，这个东西可以离线下来二维数点，树状数组维护

现在考虑找出所有修改，暴力找肯定是\(O(n^2)\)的，无法接受。

因为是询问区间\([l,r]\)内的最大值，如果在一个endpos集合中\(x<y<z\)，\((x,y),(y,z),(x,z)\)都可以做出贡献，但是\((x,z)\)的贡献是没有影响的。使用set启发式合并，每次只增加相邻的位置的贡献，复杂度\(O(n\log^2 n)\)

P3346 [ZJOI2015]诸神眷顾的幻想乡

树上的一条链一定是以叶子为根的树中一条儿子到祖先的链，因为叶子节点数很少，也就相当于20个Trie。对每一个叶子DFS一下，建出广义后缀自动机求\(\sum len[fa[i]]-len[i]\)即可

CF666E Forensic Examination

建出广义SAM，在后缀自动机上找出\(S[1,\cdots,i]\)对应的节点\(pos[i]\)，与能够匹配的最大长度\(mxlen[i]\)

找\(S(l,r)\)就是在parent树上倍增，找到\(len_u\ge r-l+1\)的深度最小的点\(u\)，这样我们就找到了\(S(l,r)\)对应的节点（子树）

开一个线段树，维护每个节点的endpos中，串编号在\([l,r]\)内的最大出现次数和对应的串，这个可以线段树合并做到\(O(n\log n)\)

找到节点之后询问即可