[学习笔记] SAM及其应用

· · 个人记录

这几天学 SAM 学懵了。写篇学习笔记整理整理。

注意，本篇博客不是 SAM 入门教程。如果想要入门，建议看OI-wiki或者一篇不错的blog

接下来叙述 SAM 的几个例题。

SP48 BEADS - Glass Beads

非常基础的一个题。

我们的SAM有一个非常重要的性质，就是说从起点开始，沿着转移走，可以走遍所有的子串，而且其中没有重复。

那么这个题的做法就非常显然。我们复制一遍原字符串，贪心地每次选取最小的转移跑 len 次就可以了。

为什么每次选取最小的一定可以跑至少 len 次？

因为我们的 SAM 串是由一个字符串复制一遍而来的。跑到的第一个状态的实际位置不会在后半段出现。

做完了。顺便有个双倍经验题P1368.

SP8222 NSUBSTR - Substrings

非常板子的一个题。题意就是统计每个长度的字符串的出现次数的最大值。

我们发现一个节点的|endpos|就是这个 endpos 等价类中所有子串的出现次数。

然后我们有一个性质，对于一个节点 u，他的|endpos|就是所有 parent 树上u的儿子的|endpos|和加上这个点是否包含一个前缀。

为什么要加是否是一个前缀呢？

我们考虑这个前缀的endpos是不可能由 u 的儿子推出来的，因为如果你要在这个位置有一个对应的儿子 v 有endpos，则maxlen_v>maxlen_u. 因为是前缀，所以前面加不了字符了，自然也就矛盾了.

至于为什么这样就可以考虑全的话可以类似地反证。

最后瞎上一个数据结构，每次枚举所有状态，把[minlen_i, maxlen_i]这个区间与|endpos_i|取max，最后单点查询就可以了

SP7258 SUBLEX

非常板子的一个题。

我们首先考虑怎么求出一个点 u 出发的子串个数 siz_u。

到了一个状态以后有两种情况

dp 一遍就好了，注意一下根节点的特判

最后类似主席树求第 k 小搞搞就可以了。

SP1811 LCS - Longest Common Substring

不会用后缀数组，太难了。

不会广义后缀自动机，连篇讲稿都找不到。

我们考虑裸 SAM 解决。

我们对于第一个字符串 a 建立 SAM。

我们考虑求一个字符串的所有子串的经典化法是求该字符串的所有前缀的后缀。

直接在 SAM 上把第二个字符串 b 的所有字符一个个放进来。设当前的状态是 p

如果一直没有就重新开始。最后对所有搞定了。

SP1812 LCS - Longest Common Substring2

不会广义后缀自动机，连篇讲稿都找不到。

我们还是对于第一个字符串 a 建立 SAM。

显然这次不可以基于每一个其他字符串搞了。我们就要在这个 SAM 上边做做文章。

考虑搞出每一个节点可以匹配到的最大值。

我们考虑对于一个前缀的所有后缀，有可能和它匹配的点一定在parent树上最优匹配点->根节点上。别的点不可能和这些后缀匹配。

然后我们发现这一串点并不能在过来的途中被经过，所以需要更新一遍。

最后因为是很多个串搞，所以要取个min。