后缀自动机（SAM）学习笔记

好吧这是第二个紫模板算法

后缀自动机简介

一个对字符串所有子串进行高度压缩后储存的数据结构，其时空复杂度均为线性。

实际上可以理解为一个压缩了的后缀 Tire，因为共用了大量节点，所以 SAM 整体来看是一个 DAG。

概念

endpos

对于字符串 $s$ 的任意子串 $t$（含空串），我们记它在 $s$ 中结束位置的下标（从 $1$ 开始）的集合为 $endpos(t)$。

特别的，空串的 $endpos=\{1,2,\dots,|s|\}$。

等价类

记 $maxlen$ 为同一等价类中最长字符串的长度，$minlen$ 为最短。

对于 $endpos$ 相同的一些子串，我们称他们为一个等价类，则有以下性质：

• 同一等价类中的任意两个子串一定呈后缀关系。
• 同一等价类中，子串长度一定互不相同，且长度一定占据 $[minlen,maxlen]$ 这个区间
• 两个等价类的 $endpos$ 要么包含要么不交。
• 若两个等价类包含，则 $endpos$ 更大的一个中所有串一定是另一个中所有串的后缀

这个证明很简单，可以自行思考~~

那么有了这些性质，我们可以通过对等价类中的位置向前拓展来构造出所有等价类，接着我们以边来表示拓展的顺序：

那么显然这构成了一棵树👆

Parent Tree

如上图👆，我们可以发现这是由等价类组成的一颗树，记 $u$ 的父节点为 $link(u)$，则有树上除了根节点外任意节点 $u$ 一定满足 $minlen(u)=maxlen(link(u))+1,minlen(u)=maxlen(link(u))+1$.

我们称这棵树为 Parent Tree，一个重要的性质为节点数量不会超过 2(n-1)，简单证明一下：

每一次拓展，生成的都是父节点的真子集，可以看做是对父节点的一种划分。本例中共有4个分割点，每一次划分的分割点各不相同。每使用一个分割点会至多形成两个新集合作为子集，所以总的节点数不会超过2(n-1)

建立 SAM

SAM 与 Parent Tree 的关系

• Parent Tree覆盖到所有子串，且每个节点都是一个等价类，所以等效于 SAM 的节点。
• Parent Tree 上面的边不是 SAM 的边，所以 Parent Tree作为一种辅助构建 SAM 的结构。

SAM，启动！

首先要明确，SAM 是使用增量构造法构造（就是一个字符一个字符往上加）。

还有一点是，SAM 构造时不需要求出 $endpos$ （给一张老师 PPT 上的图片)

好了，开始构造

对于一个状态，我们存3个东西：

struct node
{
    int len, link;
    int ch[26];
} sam[N];

其中 len 与 link 代表上文的 $maxlen$ 与 $link$，ch 储存转移

我们记上一个插入的状态为 $last$， 插入前的串为 $s$，插入的为 $c$.

接着是插入结点的过程：

1. 新建一个编号为 $cur$ 的状态
2. 为他的 $len$ 赋值为 $len(last)+1$.因为 $len$ 为最长的长度，则为 $|s|+1$，也就是 $len(last)+1$
3. 顺着 $last$ 一直往 $link(last)$ 跳，记当前的点为 $p$。因为这显然是 $s$ 的后缀，所以当没有 $c$ 的转移时，可以直接为 $p$ 连接一条向 $cur$ 的为 $c$ 的转移。
4. 直到跳到 $link(1)$ 或者 $p$ 出现了向 $c$ 的转移，停止上一步，分以下三种情况：

   1. $p=link(1)$，也就表明不会出现包含 $cur$ 的等价类，则 $link(cur)$ 指向 1

   2. 记 $q$ 为 $p$ 向 $c$ 转移到的节点，若 $len(p)+1=len(q)$，则 $link(cur)$ 指向 $q$，因为此处 $q$ 处的最长子串是由 $p$ 处增加字符得来，那么 $q$ 处的字符串就显然是 $cur$ 处的后缀（因为都是由 Parent Tree 上 $last$ 到根这一条链中的状态向 $c$ 转移），且一定是符合此条件中 $len$ 最大的一个。
      结合图片吧……

      

   3. 若$len(p)+1>len(q)$，则需要将 $q$ 的状态分割成上一种情况的和由其他状态转移的，那么将 $p$ 复制到状态 $clone$，$len(clone)$ 设为 $len(p)+1$，然后将 $link(q)$、$link(cur)$ 全部指向 $clone$，将Parent Tree 上 $p$ 到根这一条链中 $c$ 的转移转移到 $q$ 的改为转移到 $clone$.

      要不然自己模拟一下 aabab，这很显然。

      

到此，就可以构建出一个 SAM。

int last = 1, idx = 1;
struct node
{
    int len, link;
    int ch[26];
} sam[N];
void insert(char ch)
{
    int c = ch - 'a';
    int p = last, cur = ++ idx;
    sam[cur].len = sam[p].len + 1, last = cur;
    for(; p && !sam[p].ch[c]; p = sam[p].link) sam[p].ch[c] = cur;
    if(!p) sam[cur].link = 1;
    else
    {
        int q = sam[p].ch[c];
        if(sam[q].len == sam[p].len + 1) sam[cur].link = q;
        else
        {
            int clone = ++ idx;
            sam[clone] = sam[q];
            sam[clone].len = sam[p].len + 1;
            sam[q].link = sam[cur].link = clone;
            for(; p && sam[p].ch[c] == q; p = sam[p].link) sam[p].ch[c] = clone;
        }
    }
}

应用

求解 endpos 大小

为每一个插入的 $cur$ 节点赋上 1， $endpos$ 大小即为子树之和。

//...
    int cur = ++ idx, p = last; siz[cur] = 1;
//...
vector<int> e[N];
void build() {for(int i = 2; i <= idx; i ++) e[sam[i].link].push_back(i);}
void dfs(int u) {for(auto v : e[u]) dfs(v), siz[u] += siz[v];}

P3804 【模板】后缀自动机（SAM）

不同子串个数

两种方法：

1. 对于每个状态，它所包含的不同字符串个数为 $len(u)-len(link(u))$，可动态维护。
2. 令 $dp_u$ 表示从 $u$ 开始的路径数量，则 $dp_u=1+\sum_{i=0}^{25}dp_{sam_u.ch_i}$，不可动态维护。

方法二：

int dp[N];
void dfs(int u)
{
    dp[u] = 1;
    for(int i = 0; i < 26; i ++)
        if(sam[u].ch[i]) dfs(sam[u].ch[i]), dp[u] += dp[sam[u].ch[i]];
}

P2408 不同子串个数，P4070 [SDOI2016] 生成魔咒

第 k 小子串

由于借助应用一、二，可以求出从每个点往后的路径数量（区别是否可以重复），然后从根节点往下走找到目标路径。

vector<int> e[N];
void build() {for(int i = 2; i <= idx; i ++) e[sam[i].link].push_back(i);}
void dfs1(int u)
{
    for(auto v : e[u])
        dfs1(v), siz[u] += siz[v];
}

int dp[N];
void dfs2(int u)
{
    if(dp[u]) return ;
    dp[u] = siz[u];
    for(int i = 0; i < 26; i ++)
        if(sam[u].ch[i]) dfs2(sam[u].ch[i]), dp[u] += dp[sam[u].ch[i]];
}

void dfs3(int u, int k)
{
    k -= siz[u];
    if(k <= 0) return ;
    int last = 0;
    for(int i = 0; i < 26; i ++)
        if(sam[u].ch[i])
            if(k > dp[sam[u].ch[i]]) k -= dp[sam[u].ch[i]];
            else {last = i; break ;}
    cout << char(last + 'a');
    dfs3(sam[u].ch[last], k);
}

P3975 [TJOI2015] 弦论

最长公共子串

两串

对其中一个建立 SAM，将另外一个从根节点开始匹配，失败时跳 $link$ 直到继续匹配。过程中的最大匹配长度即为答案。

int p = 1, len = 0, ans = 0;
for(int i = 1; i <= m; i ++)
{
    int c = t[i] - 'a';
    if(sam[p].ch[c]) len ++, p = sam[p].ch[c];
    else
    {
        for(; p && !sam[p].ch[c]; p = sam[p].link) ;
        if(p) len = sam[p].len + 1, p = sam[p].ch[c];
        else p = 1, len = 0;
    }
    ans = max(ans, len);
}

多串

对其中一个建立 SAM，将另外的依次匹配。在串内，统计每个点上最大值（由于有多串，计算时要同时更新 $link$ 的值。串外再取最小值，最后每个节点最小值的最大值即为答案。

while(cin >> t + 1)
{
    int m = strlen(t + 1);
    int p = 1, len = 0;
    for(int i = 1; i <= m; i ++)
    {
        int c = t[i] - 'a';
        if(sam[p].ch[c]) len ++, p = sam[p].ch[c];
        else
        {
            for(; p && !sam[p].ch[c]; p = sam[p].link) ;
            if(p) len = sam[p].len + 1, p = sam[p].ch[c];
            else p = 1, len = 0;
        }
        _l[p] = max(_l[p], len);
        int f = sam[p].link;
        _l[f] = max(_l[f], min(_l[p], sam[f].len));
    }
    for(int i = 1; i <= idx; i ++) l[i] = min(_l[i], l[i]);
    memset(_l, 0, sizeof _l);
}
int ans = 0;
for(int i = 1; i <= idx; i ++) ans = max(ans, l[i]);

鸽鸽~~~