后缀自动机
基本定义
后缀自动机 (SAM) 是一种确定性有限自动机 (DFA)。(别管这个,只是出于严谨念了一边)
有一个广为人知的算法——Trie。
但是,如果用 Trie 来储存一个字符串的所有后缀 / 子串信息,结点数会达到 \(|s|^2\) 级别(下图是 abba
的后缀 Trie)。
然而,我们发现,图上有很多结点的子树完全一样(例如结点 abb
与结点 bb
),可以合并成一棵子树以减少结点数。
可以说,把 Trie 合并为一个结点最少的 DAG,就是 SAM。
\(endpos\) 等价类
对于一个子串,我们把它所有出现位置的末尾记下来,组成一个集合,就是这个子串的 \(endpos\)。
例如,在 abcdabc
中,abc
的 \(endpos\) 为 \(\{3,7\}\)。(本文中下标从 \(1\) 开始计)
我们把 \(endpos\) 集合相同的子串叫做一个 \(endpos\) 等价类。
记 \(s\) 的 \(endpos\) 集合为 \(endpos(s)\)。
引理 \(1\):若 \(s_1\) 是 \(s_2\) 的后缀,则 \(endpos(s_2) \subseteq endpos(s_1)\)
很好理解,若 \(s_1\) 是 \(s_2\) 的后缀,那么 \(s_2\) 每次出现的时候,\(s_1\) 都必然以 \(s_2\) 后缀的形式出现;
然而,\(s_1\) 还可能单独出现,即前面不直接连着 \(s_2-s_1\)。
例如在 abcdabcdbcd
中,bcd
与 abcd
就是这种关系,\(endpos(\) bcd
\()=\{4,8,10\}\),\(endpos(\) abcd
\()=\{4,8\}\)。
引理 \(2\):对于两个字符串 \(s_1,s_2\ (|s_1| \leq |s_2|)\),那么要么 \(endpos(s_2) \subseteq endpos(s_1)\),要么交集为空。
如果交集不为空,那么至少有一个 \(endpos\) 相同,
因为原串是固定的,所以两个 \(endpos\) 相同的串等于某一个前缀的两个后缀。
那么可以导出 \(s_1\) 必然是 \(s_2\) 的后缀,即证。
\(parent\) 树
为了方便,令 \(endpos("")=\{x\in \Z | 1 \leq x \leq n\}\)(即所有 \(endpos\) 的全集)。
可以发现,\(\forall s_2=c+s_1,endpos(s_2)\subseteq endpos(s_1)\)。
我们建立一棵树,一个节点代表一个 \(endpos\) 等价类,使得父亲都是儿子的后缀。(根节点是空串)
所以有 \(endpos(son) \subset endpos(father)\),注意,一个结点可能代表数个 \(endpos\) 相同的字符串。
我们定义一个数组 \(link\) 表示某个节点在 \(parent\) 树上的父亲。
而对于一堆 \(endpos\) 相同的子串,它们在后面接一个字符的方式都是相同的(都只能接 \(endpos+1\) 处的字符),所以在 DAG 中会有相同的转移,由 SAM 的最小性,它们在 SAM 中必然是同一个顶点。
SAM 存储的信息
首先来明确每个节点存的是啥:
\(link\)
(个人喜欢写 \(lnk\))
存这个等价类节点在 \(parent\) 树上的父亲。
\(len\)
每个节点代表一个 \(endpos\) 等价类,这个等价类中应有未知个字符串,设其中最长的长度为 \(len\ [\ ]\),其中最短的长度为 \(minlen\ [\ ]\)。
由于这个 \(endpos\) 等价类中已经包含了长度为 \(len\) 的和长度为 \(minlen\) 的字符串,
因为绿字符串至少有一个 \(endpos\) 与红蓝字符串相同,
所以 \(endpos(R) \subseteq endpos(G) \subseteq endpos(B)\),又 \(endpos(R)=endpos(B)\),所以 \(G\) 也在这个等价类中。
我们再来考虑 有一个 \(endpos\) 相同的 长度为 \(minlen-1\) 的 字符串,这个字符串的 \(endpos\) 必然更大(因为它不在这个等价类中)。
所以这个字符串必然在这个等价类节点的父亲中,而且必然是最长的那一个。
所以有:\(minlen=len(link)+1\)。故实际写 SAM 的时候不用记录 \(minlen\)。
\(next\)
(个人喜欢写 \(nxt\))
与 Trie 的 \(next\) 相同,存储的是这个节点可能的转移。
特别的,由于引入了 \(endpos\),所以所有转移就是所有 \(endpos+1\) 处的字符。
由于这个性质,所以在 \(parent\) 树上,父节点的转移集合包含子节点的转移集合。
存 \(next\) 用 \(map\) 或数组存都可以。
构建 SAM
构建 SAM 的时空复杂度是 \(O(n)\),是一个在线算法。
当我们每次想在字符串末尾插入一个字符 \(c\) 的时候(假设插入前字符串的长度为 \(n\)):
首先我们新建一个节点,因为 \(endpos\) 全集中增加了一个元素,必然会建出一个新的 \(endpos\) 等价类,记这个结点为 \(pos\ [\ n+1\ ]\)。
此时有 \(len\ [\ n+1\ ]=n+1\),因为这个节点中最长字符串肯定是全串。
然后,因为这个节点接在最后一个字符后面,所以所有 \(endpos\) 中存在 \(n\) 的等价类节点应当存在一个到 \(c\) 的转移。
而所有包含 \(n\) 的等价类应正好在 \(pos\ [\ n\ ]\) 到 \(pos\ [\ 0\ ]\)(根节点)的 \(parent\) 树上。
于是我们从 \(pos\ [\ n\ ]\) 开始爬 \(parent\) 树,给路上的每个节点增加一个 \(c\) 的转移到 \(pos\ [\ n+1\ ]\)。
接下来我们要给新节点(记为 \(r\))找 \(parent\) 树上的父亲。
-
如果我们一路爬到了根节点还没有找到某个到 \(c\) 的转移,那么说明字符串中没有 \(c\),
于是这个等价类中必然只包含它自己,直接 \(link\) 连到根,结束了;
-
如果我们找到某个节点存在到 \(c\) 的转移了,跳出循环,
此时祖先必然都有到 \(c\) 的转移,所以不必继续往上爬,
假设我们找到的点是 \(p\),经过到 \(c\) 的转移后到达的节点是 \(q\),
此时 \(p+c\) 这个 \(len\ [\ p\ ]+1\) 的字符串必然与新串结尾的 \(len\ [\ p\ ]+1\) 的后缀相同,
所以 \(\{endpos(q)\}\bigcup\{n+1\}\) 必然是 \(r\) 的父亲。
-
如果 \(len\ [\ q\ ]=len\ [\ p\ ]+1\),说明 \(q\) 最长的字符串恰好是 \(len\ [\ p\ ]+c\) ,所以 \(q\) 正好是 \(\{endpos(q)\}\bigcup\{n+1\}\),
直接 \(link\) 上去即可。
-
否则,我们可以把 \(q\) 分裂,把 \([\ minlen,len\ ]\) 的区间强行 copy 出一个 \(len\ [\ p\ ]+1\),
这个点应当同时作为 \(q\) 和 \(r\) 的父节点,把 \(p\) 到根节点路上所有转移到 \(q\) 的换成新节点(因为刚好长度对上)。
此时然后按上面处理即可。
-
Code
这是利用 struct 写的一份 SAM:(没有存 \(pos\),上一次存点的位置就是下一次需要的 \(pos\),根节点被设为 \(0\),根节点的父亲设为 \(-1\))。
inline void insert(char c) {
++siz; ++n;
sam[siz].len=n; Siz[siz]=1;
register int p=lst; lst=siz;
while(p!=-1&&!sam[p].nxt.count(c)) {
sam[p].nxt[c]=siz;
p=sam[p].link;
}
if(p==-1) {
sam[siz].link=0;
return ;
}
register int q=sam[p].nxt[c];
if(sam[p].len+1==sam[q].len) {
sam[siz].link=q;
return ;
}
++siz;
sam[siz]=sam[q];
sam[siz].len=sam[p].len+1;
while (p!=-1&&sam[p].nxt[c]==q) {
sam[p].nxt[c]=siz;
p=sam[p].link;
}
sam[q].link=sam[siz-1].link=siz;
return ;
}
一些证明(先咕了)
SAM 的节点数小于 \(2n\)
SAM 的转移数小于 \(3n\)
应用以及例题(先咕了)
广义后缀自动机
看完 SAM,发现 SAM 实现了单个字符串的后缀 Trie,干掉了 KMP。
那么 SAM 能不能干掉 AC 自动机呢?
答案是可以的,这就是广义 SAM。