RenaMoe's Blog

念念不忘，必有回响

0%

总结 SAM

发表于 更新于 分类于 ， Valine：

\(\rm SAM:\ Suffix\ Automaton\) ，后缀自动机。

远古博客，有许多纰漏，慎重食用！

难理解，但代码好写（当初敲完模板题没总结，现在忘光了QAQ）

总体上是 后缀 trie + parent tree ，构成一个可以表示所有子串的 DAG

福利：后缀自动机可视化

推荐博客：

这博客主要是我总结自己不好理解的地方，不是很全面

声明：本文中图片大部分为 BANANA 从他人博客盗来的借鉴的，一些语言表达借鉴于 KesdiaelKen 的博客 ，若有侵权请 联系BANANA 删除

思路

前置

先了解几个概念：

后缀 trie ：把字符串的每一个后缀插入到 trie 树里

一个普通的后缀 trie ，有很大部分节点是可以压缩的

endpos 集合 ：一个子串在原串出现的位置（可能出现多次）的右端点集合

比如一个串“banana”

\(endpos(b)=\{1\},\ endpos(a)=\{2,4,6\}\)

\(endpos(an)=\{3,5\},\ endpos(ana)=\{4,6\}\)

parent tree ：一个子串前面添加一个或几个字符，可以将他的 endpos 集合分割，endpos 集合之间便有了父子关系

parent tree 上每一个节点表示的 endpos 集合唯一地表示一个后缀集合

不好举例，自己手模吧

构造

将后缀 trie 和 parent tree 结合起来便是 SAM 的 DAG

那么一条路径表示原串的一个子串，一个节点 x 表示根节点到 x 路径形成的所有串的 endpos 集合

SAM 常见的增量构造：将字符串从前到后一个一个字符插进去（离线构造窝不会）

先确定一些量：

  • \(fa[x]\) ：x 节点表示的集合在 parent tree 上的父亲

  • \(len[x]\) ：x 节点表示的集合中最长的串的长度

    如果设最短的串长为 \(minlen[x]\) ，那么 \(len[fa[x]]+1=minlen[x]\) ，即 parent tree 上的分割关系

我们考虑从后面插入一个字符 c，会有什么变化：

  • 多出新串的后缀
  • 新串后缀的 endpos 集合改变

那么在 trie 的意义上要把旧串所有后缀的后面加上字符 c

在 SAM 上实现就是先新建节点 np

然后把最后一个节点 p、它在 parent tree 的父亲以及祖先的 c 儿子设为该节点（相当于压缩地遍历旧串的所有后缀）

并且 \(len[np]=len[p]+1\)

1
2
3
4
int p = last, np = last = ++cnt;
len[np] = len[p] + 1;
while (p && !ch[p][c])
    ch[p][c] = np, p = fa[p];

  1. 如果这些祖先都没有 c 儿子，到达最高的祖先就是根节点

    说明字符 c 是一个新字符，parent tree 上根节点多一个儿子：只有位置 c 的 endpos 集合

1
if (!p) fa[np] = 1;

  1. 那么如果有一个祖先 p 已经有了 c 儿子，设它为 q

    说明旧串有子串的结尾是 c 字符，那么就要看这个 q 的 len 了

    • \(len[q]=len[p]+1\)

      说明 q 在插入时 p 就是最后一个节点了

      那么根到 q 点表示的子串都是根到 np 表示的子串的后缀

      在 parent tree 上，q 是 np 的父亲

    • \(len[q]>len[p]+1\)

      在 parent tree 上，q 和 np 是兄弟

      那么就新建一个 nq （复制一份 q ）作为它俩的父亲

      将之前 p 及其祖先指向 q 的 c 儿子全指向 nq 即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int q = ch[p][c];
    if (len[q] == len[p] + 1)
        fa[np] = q;
    else {
        int nq = ++cnt;
        memcpy(ch[nq], ch[q], sizeof ch[q]);
        len[nq] = len[p] + 1;
        fa[nq] = fa[q], fa[q] = fa[np] = nq;
        while (p && ch[p][c] == q)
            ch[p][c] = nq, p = fa[p];
    }

code

完整构造代码，看起来一堆 while 却是\(O(n)\)。

注意点数是 \(2n\) 规模。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct Suffix_Automaton {
    int cnt, last;
    int fa[N<<1], ch[N<<1][30], len[N<<1];
    inline Suffix_Automaton() {
        last = cnt = 1;
    }
    inline void add(int c) {
        int p = last, np = last = ++cnt;
        len[np] = len[p] + 1;
        while (p && !ch[p][c])
            ch[p][c] = np, p = fa[p];
        if (!p) fa[np] = 1;
        else {
            int q = ch[p][c];
            if (len[q] == len[p] + 1)
                fa[np] = q;
            else {
                int nq = ++cnt;
                memcpy(ch[nq], ch[q], sizeof ch[q]);
                len[nq] = len[p] + 1;
                fa[nq] = fa[q], fa[q] = fa[np] = nq;
                while (p && ch[p][c] == q)
                    ch[p][c] = nq, p = fa[p];
            }
        }
    }
} SAM;

应用

  • 判断子串

    直接在 SAM 上跑，跑完没到 NULL 即为子串

  • 求不同子串个数

    设 \(f[i]\) 为从 i 点出发的子串， \(f[i]=\sum_{(i,j)\in Edge}{f[j]+1}\)

    好像还可以直接求 \(\sum{(len[i]-len[fa[i]])}\) ，因为 SAM上无重复子串

  • 待更~

题目

BANANA 由于过菜，还不会写几道题~

求出 S 的所有出现次数不为 1 的子串的出现次数乘上该子串长度的最大值

一个子串的出现次数即在 parent tree 上该子树的 size

暴力建出 parent tree，或者拓扑一下 DAG ，统计

每次向后插入一个字符，并求每次操作后不同子串个数

显然 SAM 应用在求不同子串个数 \(\sum{(len[i]-len[fa[i]])}\)

每次只增加一个 len 影响总个数的节点，ans += len[x] - len[fa[x]]，于是每次 \(O(1)\) 统计答案

大坑：“字符”范围 1e9 ，每个节点要用 map 存儿子

  • 待更~