Sam做题记录

求一个串中本质不同的子串数

显然，答案是 $\sum len[i]-len[fa[i]]$

求一个串每个长度出现次数的最大值

求出fail树每个点的size就是该点的出现次数，由于答案是（非严格）单调减的，每个点更新一下 $ans[len[i]]$

求几个数字串本质不同的子串所代表的数的和， $mod\ 10^9+7$

先建一下广义sam，在转移边上bfs更新答案

给定一个字符串S，询问另一个字符串T的子串和S的子串匹配数。匹配的定义为两个串循环同构。

对S建Sam，把T倍长之后在Sam上跑，如果一个位置匹配长度大于|T|，那么沿着fail树向上跳到 $len[i]>=|T|$ 的最小的 $len[i]$ ，如果没有被更新过那么更新答案

给定多个字符串，求每个字符串只属于他自己的本质不同的子串数

建广义Sam，如果一个状态他在多个字符串中出现，那么他没有贡献，否则给他所在的字符串贡献 $len[i]-len[fa[i]]$

给定一个长度为 $n$ 且仅包含小写英文字母的字符串 $S$。你有一个字符串 $T$，初始为空串。

你可以进行 $n$ 次操作，每次操作你可以在 $T$ 的前端或末尾加入一个任意字母。记第 $i$ 次操作后 $T$ 在 $S$ 中的出现次数为 $f_i$，你需要最大化 $ans =\sum_{i}^{} f_i$。

对S建Sam，在末尾加入字母就是沿着匹配边走，在前面加字母就是在fail树往下走，直接把这些边全连上跑拓扑就行了

给定一棵无根树，每个点有一个字符，求本质不同的子串数，叶子节点不超过20个

注意到最后那个条件，直接每个叶子拎出来，插到sam里，然后同第一题

给定一棵Trie，求不同子串数和第K小子串

建广义Sam，第一问不说了，第二问先求出每个点沿着转移边能走多少条路，然后按位贪心

给两个小写字母串A，B，请你计算：

(1) A的一个最短的子串，它不是B的子串

(2) A的一个最短的子串，它不是B的子序列

(3) A的一个最短的子序列，它不是B的子串

(4) A的一个最短的子序列，它不是B的子序列

建Sam和序列自动机（就是求出 $next[i][c]$ 数组，表示第 $i$ 个位置下一个字符 $c$ 的位置）

然后几个询问都是在某两个自动机上跑BFS

求两个字符串的最长公共字串，两个字符串相等的条件是它们至多有一个位置不同

考虑暴力：枚举两个字符串不同的位置 $i, j$ ，那么答案为 $lcs(a_{1\dots i - 1},b_{1\dots j -1}) + 1 + lcp(a_{i + 1 \dots |a|},b_{j+1\dots|b|})$

假设我们知道 $i, j$ ，那么这个值可以在 SAM 或者 SA 上查出来（把两个串连一下，正反各建一个即可）

考虑优化这个枚举的过程

根据 SA，如果我们知道如果 $i, j$ 的 $rank$ 越接近，那么它的 LCP 就越大，那么可以想到用set维护一下这个东西

LCS是什么东西？两个点在 SAM 上的对应节点的在 $ parent $ 树上的 LCA 的 $len$ 就是它们的 LCS！

因此，在 $parent$ 树上启发式合并，然后像启发式那样去查就行了

复杂度 $O(nlog^2n)$ 好像可以一个 $log$ 不过我还暂时不会。。

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数

就两个串，建一下广义 SAM ，然后对每个串记录一下每个节点的 $size$ 乘一下加起来即可

给定字符串 $S$ ，多次询问子串s[a..b]的所有子串和s[c..d]的最长公共前缀的长度的最大值

首先反着建 SAM，$lcp$ 就转化为 $lcs$ ，二分答案 $ans$，然后就转化为问 $endpos$ 为 $c$ 的 $len \ge ans$ 的节点的 $endpos$ 集合中是否包含 $a\dots b - ans+1$ 的某个值，线段树合并求 $endpos$ 然后查一下就行了。注意每次询问还要找到最小的 $len \ge ans$ 的节点，在 $parent$ 树上倍增即可