SAM 学习笔记
前言
老年选手发现自己还不会后缀自动机。
老年选手觉得这非常离谱。
老年选手决定学一下。
正片
1
考虑怎么在一个 DAG 上表示出一个字符串的所有子串。
最简单的方法就是建一个 trie，把它的每个后缀扔进去。
那么它有什么性质呢？
- 有一个源点，若干个终止点。边代表一个字符。从源点到任意一个节点的任意路径可以形成一个原串的子串。从源点到任意节点的任意路径不能形成的字符串均不是原串子串。简单来讲，这个图可以表示且仅可以表示原串的所有子串。
- 从源点到任意终止节点的路径均为原串后缀。
- 从源点出发的任意两条不同路径形成的字符串不相同。
但是，如果直接建 trie，节点数是 \(O(n^2)\) 的。事实上，图中很多节点都可以合并，比如下图，两个黄白黄的子树就可以合并。
现在要解决的问题是，构造一个节点数，边数尽量少的 DAG 满足上面三个条件。
2 后缀自动机的一些性质
一些定义：
对于一个子串，它在原串中可能出现在若干的位置。而一个子串 \(s\) 出现的这些位置的右端点标号组成的集合，我们称之为 \(endpos(s)\) 。如下图，当原串为 \(abcab\) 时，\(endpos(ab) = \{2,5\}\) 。
下面有几个结论，比较重要。
2.1 如果两个子串的 \(endpos\) 相同，则其中一个子串必然为另一个的后缀
2.2 对于任意两个子串 \(s\) 和 \(t\) \((len_s \leq len_t)\) ，要么 \(endpos(t) \subset endpos(s)\)，要么 \(endpos(t) \cap endpos(s) = \emptyset\)
2.3 对于 \(endpos\) 相同的子串，我们把它们归为一个 \(endpos\) 等价类。对于任意一个 \(endpos\) 等价类，他们中的字符串长度连续，并且短的字符串是长的字符串的后缀
2.4 \(endpos\) 等价类个数的级别为 \(O(n)\)
对于一个类，其中有最长的一个子串 \(p\)。在 \(p\) 第一个字符前增加一个字符得到 \(t\)，使得 \(t\) 是原串子串。那么 \(t\) 与 \(p\) 并不在一个等价类内，且有 \(endpos(t) \subset endpos(p)\)。可以看作是对 \(endpos(p)\) 集合的一个分割，最终形成的集合个数不会超过 \(2n\)
所以类之间就有了父子关系。
我们称上图这棵树为 \(parent \ tree\)
2.5 在一个类 \(a\) 中，我们称最长子串的长度为 \(len(a)\)，最短子串的长度为 \(minlen(a)\)。对于后缀树上存在父子关系的两个类，则 \(len(fa(a))+1 = minlen(a)\)
在一个类的最长子串前再添加一个字符，形成的字符串属于其儿子中的一类，且是它所属的类中最短的一个。
因此，我们只需要保存 \(len\) 和 \(fa\) 即可，\(minlen\) 可由其父亲推出
我们定义 \(longest(a)\) 表示 \(a\) 中最长子串，\(shortest(a)\) 表示 \(a\) 中最短子串
把每一个类的最长子串写在节点旁长下面这样，原串是 \(aababa\)
3 构造
后缀自动机通过单个地增加字符实现构造
给出代码
struct __{int ch[26],fa,len;}t[N];
int lst=1,cnt=1;
inline void insert(char c)
{
int p=lst,node=++cnt; lst=node;
t[node].len=t[p].len+1;
for (;p&&!t[p].ch[c];p=t[p].fa) t[p].ch[c]=node;
if (!p) t[node].fa=1;
else
{
int q=t[p].ch[c];
if (t[q].len==t[p].len+1) t[node].fa=q;
else
{
int clone=++cnt;
rep(i,0,25) t[clone].ch[i]=t[q].ch[i];
t[clone].fa=t[q].fa;
t[clone].len=t[p].len+1;
t[q].fa=clone;
for (;p&&t[p].ch[c]==q;p=t[p].fa) t[p].ch[c]=clone;
t[node].fa=clone;
}
}
}
结构体的 \(len\) 和前面的定义一致，\(fa\) 表示 \(parent\ tree\) 上的父亲，\(ch\) 和 \(trie\) 里的边意义相近。
\(lst\) 是此前最长的前缀所属的节点的编号。
注意初始时，\(lst=cnt=1\)，因为我们手动加入了一个空串。
记 \(node\) 代表的串为 \(s\)，\(p\) 代表的串为 \(t\)。
那么显然，\(s\) 是 \(t\) 加一个字符 \(c\) 得到，同样地，\(s\) 的后缀也可以通过 \(t\) 的后缀加一个字符 \(c\) 得到，那么 for 一下 \(p\) 在 \(parent \ tree\) 上的祖先。这一步可以理解为压缩地遍历一个串地所有后缀。
for (;p&&!t[p].ch[c];p=t[p].fa) t[p].ch[c]=node;
对于节点 \(p\) ，如果它没有 \(c\) 边，即 \(longest(p)+c\) 并非旧串子串，那么就建一条新边到 \(node\)。此时 $endpos(longest(p)+c) $ 等于 \(endpos(s)\) ，所以它们是一个等价类。如果它有 \(c\) 边，此时 \(longest(p)+c\) 已经在旧串中出现过，那它的 \(endpos\) 不等于 \(n\)，就不合法，\(break\)。
if (!p) t[node].fa=1;
如果已经遍历完了旧串所有的后缀，且它们加 \(c\) 都不是旧串地子串，说明不可能存在除节点 1 以外的祖先（因为也会遍历空串）
else
{
int q=t[p].ch[c];
if (t[q].len==t[p].len+1) t[node].fa=q;
else
{
int clone=++cnt;
rep(i,0,25) t[clone].ch[i]=t[q].ch[i];
t[clone].fa=t[q].fa;
t[clone].len=t[p].len+1;
for (;p&&t[p].ch[c]==q;p=t[p].fa) t[p].ch[c]=clone;
t[q].fa=t[node].fa=clone;
}
}
但是，如果 \(p\) 在第一个有 \(c\) 边的祖先停下了，记 \(p\) 通过 \(c\) 边连向 \(q\)。
这时，\(q\) 内的子串是 \(s\) 的后缀。所以 \(q\) 是 \(node\) 在后缀树上的祖先。
注意到，后缀树上的节点，满足 \(len(fa(a) ) + 1 =minlen(a)\)。
那么，此时有两种情况。
第一种：\(len(p)+1= len(q)\)
因为 \(longest(p)+c\) 是新串后缀，又 \(len(p)+1=len(q)\)，所以\(longest(q)=longest(p)+c\) 是新串后缀。又因为 \(q\) 内的所有串都是 \(longest(q)\) 的子串，所以它们的 \(endpos\) 集合整体并上了 \(\{n\}\)，它们的 \(endpos\) 集合还是相同的，直接把 \(node\) 的 \(fa\) 置为 \(q\) 即可
第二种：\(len(p)+1 < len(q)\)
那么在加入新点之后，\(q\) 里长度 \(\leq len(p)+1\) 的串的 \(endpos\) 集合并上了 \(\{n\}\)。长度 \(> len(p)+1\) 的串的 \(endpos\) 集合不变。所以 \(q\) 就不再符合等价类的定义了。这时要把\(q\) 分裂，变成 \(clone\) 和 \(q\)，其中 \(clone\) 包含原 \(q\) 中长度 \(\leq len(p)+1\) 的子串，\(q\) 中包含原 \(q\) 中长度 \(>len(p)+1\) 的子串。
那么考虑 \(clone\) 的信息。首先 \(len(clone) = len(p)+1,fa(clone) = fa(q)\)。对于 \(clone\) 的字母出边，和 \(q\) 是一样的。因为原 \(q\) 中的所有子串都是新串的后缀，在它们之后加字符，\(endpos\) 集合不会改变。
然后这时，\(fa(q) = clone\)，因为它满足 \(len(clone)+1 = minlen(q)\)，并且 \(endpos(q) \subset endpos(clone)\)。
这时，再考虑 \(p\) 在后缀树上的祖先。如果它的 \(c\) 边指向原 \(q\)，因为 \(longest(p)+1 = longest(clone)\)，所以对于 \(p\) 的祖先的每一个子串，它的 \(endpos\) 集合会比之前并上 \(\{n\}\)。所以要把它们的 \(c\) 边指向 \(clone\)。如果它的 \(c\) 边不指向原 \(q\)，那么它会指向原 \(q\) 后缀树上的一个祖先。它们的祖先的 \(endpos\) 集合都整体地并上了 \(\{n\}\)，不用更改。
最后，我们再考虑 \(node\) 的信息。它的后缀树上的父亲应该是 \(clone\)，因为 \(endpos(clone)\) 中含有 \(\{n\}\)，而 \(endpos(q)\) 中不含。
4 应用
这我咋知道，我又没做过题（