SAM 基础练习题

让我们来写一点 SAM 的例题。

endpos 集合大小就是这点包含的一堆子串(在原串中)的出现次数。

设 \(lcs(i,j)\) 为前缀 \(i,j\) 的最长公共后缀长度,其等于 \(parent\) 树上 \(LCA\) 的 \(len\) 值。

要找到一个子串在 SAM 中的位置，可以先记录所有 $ [1,i] $ 的结点，然后开始向上倍增，找到最小的 $ len $ 大于区间长度的结点即可。

P3804 【模板】后缀自动机（SAM）

endpos 集合大小就是这点包含的一堆子串(在原串中)的出现次数。

所以直接建树统计子树大小算贡献即可。

P2408 不同子串个数

考虑每加入一个点，它相较于它后缀树上的父亲多的子串个数其实就是 $ len(i) - len(fa(i)) $，因为 $ min(len(i))=len(fa(i))+1 $，且一个等价类中的所有串长是连续的。

P3975 [TJOI2015] 弦论

若不同位置的相同子串算作一个的话，那么每一个 SAM 结点的大小都应该算所 1。

但若不同位置的相同字串算作多个的话，那么每一个 SAM 结点的大小应该算作 endpos 集合大小。

然后直接在 SAM 上像主席树找第 k 大那样找就行了。

P5357 【模板】AC 自动机

你拿文本串建 SAM，然后拿模式串去 SAM 上面匹配，最终到的那个结点的 endpos 等价类集合大小即为这个模式串在文本串中的出现次数。

能不能过你别管，反正正确性是对的（

SP1811 LCS - Longest Common Substring

求两个串的最长公共子串。

你直接对一个串建 SAM，另一个串在上面跑即可。

具体的，从前往后扫模式串的每一个字符。

若有这条出边，跳到下一个结点，len++

否则若没有这条出边，则重复往上跳直到跳到有这条出边为止。

若跳到根节点，len=0 u=1 继续匹配。

否则 u 跳到下一个结点，len 变为当前节点的长度加一。

P4248 [AHOI2013] 差异

设 \(lcs(i,j)\) 为前缀 \(i,j\) 的最长公共后缀长度,其等于 \(parent\) 树上 \(LCA\) 的 \(len\) 值。

那么我们基于反串建 parent 树，然后求出所有结点的 endpos 等价类大小，在结点上算贡献即可。

P4094 [HEOI2016/TJOI2016] 字符串

好聪明，受教了。

题目要你求串 $ s[a,b] $ 的所有子串与 $ s[c,d] $ 的最长公共前缀。

注意到和 $ [c,d] $ 求最长公共前缀，所以我们直接二分这个最长公共前缀的长度。

问题转化为查询 $ [c,c+mid-1] $ 这个子串在 $ [a,b] $ 中是否出现过。

首先我们假设可以求出 $ [c,c+mid-1] $ 所在 SAM 上的结点 $ p $。

那么我们其实就是要查询在结点 $ p $ 的等价类集合上是否存在在 $ [a+mid-1,b] $ 区间的值。

这个直接线段树合并维护 endpos 等价类集合即可。

注意不能垃圾回收，因为你最后还要查询每个结点上的答案。

然后就是处理如何找到 $ [c,c+mid-1] $ 这个子串在 SAM 上的结点 $ p $ 了。

直接考虑倍增，你直接从 $ [1,c+mid-1] $ 这个位置开始跳，向上倍增跳到第一个 $ len \ge mid $ 的位置即可。

CF666E Forensic Examination

求 $ s[l,r] $ 在 $ [a,b] $ 个串之间出现次数最多的是哪个，出现次数最多为多少？

会了上一题就很好做了，你直接给所有模板串建 GSAM，然后倍增找到 $ [l,r] $ 在 GSAM 上的结点位置，线段树合并维护 endpos 等价类之后直接在线段树上查询 $ [a,b] $ 的最值和最值的位置即可。