SAM 学习笔记

目录

后缀自动机

基本定义

后缀自动机 (SAM) 是一种确定性有限自动机 (DFA)。(别管这个,只是出于严谨念了一边)

有一个广为人知的算法——Trie。

但是,如果用 Trie 来储存一个字符串的所有后缀 / 子串信息,结点数会达到 \(|s|^2\) 级别(下图是 abba 的后缀 Trie)。

SAM 学习笔记

然而,我们发现,图上有很多结点的子树完全一样(例如结点 abb 与结点 bb),可以合并成一棵子树以减少结点数。

可以说,把 Trie 合并为一个结点最少的 DAG,就是 SAM。

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 中,bcdabcd 就是这种关系,\(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\ [\ ]\)。

SAM 学习笔记

由于这个 \(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。

构建广义 SAM

上一篇:P4070 [SDOI2016]生成魔咒 - SAM


下一篇:七年程序员炫耀:阿里跳槽拼多多,80万涨到160万!值不值得去?