后缀自动机 学习笔记

作者: xht37 分类: 笔记 发布时间: 2020-03-14 21:40

Visits: 786

因为 SA 就很有用了,所以一直不想学 SAM。突然不知道为什么就想学了,可能是为了吊打兔兔吧。
后缀自动机 (SAM) 是一个能解决许多字符串相关问题的有力的数据结构。
直观上,SAM 可以理解为将字符串的所有子串高度压缩至理论复杂度下界 $\mathcal O(n)$ 的形式。

确定有限状态自动机 (DFA)

我们先要了解,什么是确定有限状态自动机 (DFA)

定义

一个 DFA 可以看成一张有向图,由五个部分构成:

  1. 状态集合 $Q$:图中的点。
  2. 字符集 $\Sigma$:所有合法字符的集合。
  3. 转移函数 $\delta(v,c)$:图中的边,其中 $v$ 和返回值都是一个状态,分别对应一条边的起点和终点,$c \in \Sigma$,表示这条边上的字符。
  4. 起始状态 $S$:$S \in Q$,是一个特殊的状态。
  5. 接受状态集合 $F$:$F \subseteq Q$,是一组特殊的状态。

作用

DFA 可以识别字符串。

当 DFA 读入字符串 $s$ 时,从 $S$ 开始按照 $\delta(v,c)$ 一个一个字符地转移。

特别地,如果某个状态 $v$ 没有字符 $c$ 的转移,则令 $\delta(v,c) = N$,$N$ 只能转移到 $N$,且 $N \notin F$。

如果读入完 $s$ 后处在 $F$ 内,就称这个 DFA 接受 $s$。

扩展定义转移函数 $\delta(v,s)$,其中 $s$ 是一个由 $\Sigma$ 内的字符构成的字符串,则 $\delta(v,s) = \delta(\delta(v,s[1]),s[2:|s|])$。

一个 DFA 是否接受 $s$,等价于求 $[\delta(S, s) \in F]$ 的值。

后缀自动机 (SAM)

后缀自动机 (SAM) 是接受且仅接受字符串 $s$ 的所有后缀的最小 DFA

构造

$\operatorname{rightpos}$ 等价类

在一些教程中,$\operatorname{rightpos}$ 也被称作 $\operatorname{endpos}$。本文选择 $\operatorname{rightpos}$,是因为同样存在定义类似的 $\operatorname{leftpos}$,而不存在 $\operatorname{beginpos}$ 的叫法。

对于 $s$ 的子串 $t$,记 $\operatorname{rightpos}(t)$ 为 $s$ 中 $t$ 的所有结束(即最右边的字符)位置。如对于字符串 $\texttt{abcbc}$,$\operatorname{rightpos}(\texttt{bc}) = 3,5$。特别地,空串的 $\operatorname{rightpos}$ 定义为 $0,1,\cdots,|s|$。

若两个非空子串 $t_1,t_2$,满足 $\operatorname{rightpos}(t_1) = \operatorname{rightpos}(t_2)$,则将他们划分到一个 $\operatorname{rightpos}$ 等价类中。

SAM 中的每个状态都对应着一个 $\operatorname{rightpos}$ 等价类,其中 $S$ 对应着空串所在的等价类。

$\operatorname{rightpos}$ 性质

  • 考虑一个子串 $t$,我们每次去掉 $t$ 的首字母,则它所在的 $\operatorname{rightpos}$ 要么不变,要么会增加若干个新位置。
    形式化地,对于两个子串 $t_1,t_2$,不妨设 $|t_1| \le |t_2|$:
    若 $t_1$ 为 $t_2$ 的后缀,则 $\operatorname{rightpos}(t_2) \subseteq \operatorname{rightpos}(t_1)$;
    否则,说明 $t_2$ 所在的位置 $t_1$ 都不在,即 $\operatorname{rightpos}(t_1) \cap \operatorname{rightpos}(t_2) = \varnothing$。
  • 反过来考虑更强一点的性质,如果若干个子串的 $\operatorname{rightpos}$ 一样,意味着它们在 $s$ 中的出现位置一样,且它们一定是由一个子串 $t$ 不断去掉首字母,但还未能增加新位置时的所有子串构成的。
    因此,在一个 $\operatorname{rightpos}$ 等价类中,较短的子串为较长的子串的后缀,且所有子串的长度恰好覆盖一个区间

后缀链接 $\operatorname{parent}$

对于一个不是 $S$ 的状态 $v$,设它对应的等价类中最的子串为 $t$。

后缀链接 $\operatorname{parent}(v) = \operatorname{rightpos}(t[2:|t|])$。

另外,对于一个状态 $v$,记 $\operatorname{len}(v)$ 表示它对应的等价类中最的子串的长度。特别的,$\operatorname{len}(S) = 0$。

$\operatorname{parent}$ 性质

  • 依然考虑不断去掉一个子串 $t$ 的首字母:
    如果还未能增加新位置,则还在同一个 $\operatorname{rightpos}$ 等价类中;
    否则,会跳到其 $\operatorname{parent}$ 等价类中。
    因此,对于一个不是 $S$ 的状态 $v$,将其视作 $\operatorname{rightpos}$ 集合,有 $v \subseteq \operatorname{parent}(v)$。
  • 根据上条性质,对于一个不是 $S$ 的状态 $v$,它对应的 $\operatorname{rightpos}$ 等价类中,子串的长度区间为 $(\operatorname{len}(\operatorname{parent}(v)), \operatorname{len}(v)]$,即 $v$ 对应的子串数量为 $\operatorname{len}(v) – (\operatorname{len}(\operatorname{parent}(v))$
  • 所有 $\operatorname{parent}$ 构成一棵以 $S$ 为根的树,我们称其为 $\operatorname{parent}$ 树。

构造 SAM

一开始 SAM 只包含一个状态 $S$,编号为 $0$。为了方便,不妨令 $\operatorname{parent}(S) = -1$。

考虑依次添加字符,同时维护每个状态的 $\operatorname{len}$,$\operatorname{parent}$ 和转移。

令 $l$ 表示任意时刻整个字符串对应的状态,每次添加一个字符 $c$ 的过程如下:

  1. 创建一个新的状态 $w$,并将 $\operatorname{len}(w)$ 设为 $\operatorname{len}(l) + 1$。
  2. 从 $l$ 开始遍历 $\operatorname{parent}$:
    • 如果当前状态不存在字符 $c$ 的转移,则添加一个到 $w$ 的转移。
    • 如果当前状态存在字符 $c$ 的转移,则将这个状态标记为 $p$,转移到的状态标记为 $q$,然后跳出遍历。
  3. 接下来有三种情况:
    1. 如果始终没有状态存在字符 $c$ 的转移,则将 $\operatorname{parent}(w)$ 设为 $0$,然后退出。
    2. 否则,若 $\operatorname{len}(p) + 1 = \operatorname{len}(q)$,则将 $\operatorname{parent}(w)$ 设为 $q$,然后退出。
    3. 否则,再创建一个新的状态 $k$,将 $q$ 的 $\operatorname{parent}$ 和转移复制到 $k$ 上,将 $\operatorname{len}(k)$ 设为 $\operatorname{len}(p) + 1$,将 $\operatorname{parent}(w)$ 和 $\operatorname{parent}(q)$ 都设为 $k$。然后从 $p$ 往回遍历 $\operatorname{parent}$,若存在到 $q$ 的转移,则将转移重定向到 $k$ 上。
  4. 更新 $l$,即将 $l$ 设为 $w$。

最后,我们再从 $l$ 遍历一次 $\operatorname{parent}$,则 $F$ 即由遍历到的状态构成。

复杂度

如果转移用 map 存储,则时间复杂度为 $\mathcal O(n \log |\Sigma|)$,空间复杂度为 $\mathcal O(n)$。

如果转移用数组存储,同时借助链表,则时间复杂度为 $\mathcal O(n)$,空间复杂度为 $\mathcal O(n |\Sigma|)$。如果不借助链表,时间复杂度为 $\mathcal O(n |\Sigma|)$,空间复杂度为 $\mathcal O(n |\Sigma|)$。

状态数和转移数上界

对于 $|s| \ge 2$ 的字符串,状态数 $\le 2 |s| – 1$,上界可以在 $\texttt{abb}\dots\texttt{b}$ 达到。

对于 $|s| \ge 3$ 的字符串,转移数 $\le 3 |s| – 4$,上界可以在 $\texttt{abb}\dots\texttt{bc}$ 达到。

性质

  • $s$ 的子串和 SAM 中从 $S$ 开始的路径一一对应。
    对于一个非 $S$ 状态 $v$,$v$ 对应的 $\operatorname{rightpos}$ 等价类大小 $=$ $v$ 对应的子串数量 $=$ 从 $S$ 开始到 $v$ 的路径数量 $=$ $\operatorname{len}(v) – (\operatorname{len}(\operatorname{parent}(v))$。
  • 称 $s$ 的前缀在 SAM 上对应的节点为终点节点
    对于一个非 $S$ 状态 $v$,$v$ 对应的 $\operatorname{rightpos}$ 集合 $=$ 其 $\operatorname{parent}$ 树的子树内的终点节点所对应前缀的位置 $=$ $v$ 对应的子串在 $s$ 中出现的位置。
    根据此条性质,我们可以方便地采用线段树合并求出 $\operatorname{rightpos}$ 集合。
  • 说白了,SAM 中的概念,包括 $\operatorname{rightpos}$、$\operatorname{parent}$、终点节点、前缀、后缀、子串、路径,全都能串起来。
    串起来之后,随便组合就有各种各样的性质。
    例如,$s$ 的任意两个前缀对应的终点节点在 $\operatorname{parent}$ 树上的 LCA 所对应的最长子串就是这两个前缀的最长公共后缀。

应用

【模板】P3804 【模板】后缀自动机 (SAM)

根据:

  • 对于一个非 $S$ 状态 $v$,$v$ 对应的 $\operatorname{rightpos}$ 集合 $=$ 其 $\operatorname{parent}$ 树的子树内的终点节点所对应前缀的位置 $=$ $v$ 对应的子串在 $s$ 中出现的位置。

每个前缀所在的状态有贡献 $1$。

那么,对每个状态求出其 $\operatorname{parent}$ 树上的子树贡献和,然后乘上这个状态的 $\operatorname{len}$,最后取 $\max$ 即可。

const int N = 1e6 + 7;
struct SAM {
    int n, l, ch[N<<1][26], len[N<<1], pa[N<<1], t;
    char s[N];
    inline void init() { pa[0] = -1; }
    inline void add(int c) {
        int w = ++t, p = l;
        len[w] = len[l] + 1;
        while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
        if (!~p) return pa[l=w] = 0, void();
        int q = ch[p][c];
        if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
        int k = ++t;
        pa[k] = pa[q], memcpy(ch[k], ch[q], sizeof(ch[k]));
        len[k] = len[p] + 1, pa[w] = pa[q] = k;
        while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
        l = w;
    }
    inline void build() {
        init();
        for (int i = 1; i <= n; i++) add(s[i] - 'a');
    }

    int cnt[N<<1];
    ll ans;
    vi e[N<<1];
    void dfs(int x) {
        for (int y : e[x]) dfs(y), cnt[x] += cnt[y];
        if (cnt[x] > 1) ans = max(ans, 1ll * cnt[x] * len[x]);
    }
    inline void calc() {
        for (int i = 1, p = 0; i <= n; i++) p = ch[p][s[i]-'a'], ++cnt[p];
        for (int i = 1; i <= t; i++) e[pa[i]].pb(i);
        dfs(0), print(ans);
    }
} sam;

int main() {
    rds(sam.s, sam.n);
    sam.build(), sam.calc();
    return 0;
}

【例题】P4070 [SDOI2016]生成魔咒

动态子串数。

每加入一个字符,本质不同的子串数就会加 $\operatorname{len}(l) – \operatorname{len}(\operatorname{parent}(k))$ 个。

【例题】SP7258 SUBLEX – Lexicographical Substring Search

第 $k$ 小子串。

由于 SAM 是个 DAG,因此设 $cnt_i$ 表示从 $i$ 开始的路径条数,拓扑排序后再 DAG 上 dp。

这里拓扑排序可以利用基数排序,借助转移一定是从 $\operatorname{len}$ 小的往大的即可。

找答案时,从根开始贪心地找。

const int N = 9e4 + 7;
struct SAM {
    int n, l, len[N<<1], pa[N<<1], t;
    char s[N];
    map<char, int> ch[N<<1];
    inline void init() { pa[0] = -1; }
    inline void add(char c) {
        int w = ++t, p = l;
        len[w] = len[l] + 1;
        while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
        if (!~p) return pa[l=w] = 0, void();
        int q = ch[p][c];
        if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
        int k = ++t;
        pa[k] = pa[q], ch[k] = ch[q];
        len[k] = len[p] + 1, pa[w] = pa[q] = k;
        while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
        l = w;
    }
    inline void build() {
        init();
        for (int i = 1; i <= n; i++) add(s[i]);
    }

    int b[N<<1], c[N];
    ll cnt[N<<1];
    inline void sort() {
        for (int i = 1; i <= t; i++) ++c[len[i]];
        for (int i = 1; i <= n; i++) c[i] += c[i-1];
        for (int i = 1; i <= t; i++) b[c[len[i]]--] = i;
        for (int i = t; ~i; i--) {
            int x = b[i];
            cnt[x] = 1;
            for (auto o : ch[x]) cnt[x] += cnt[o.se];
        }
    }
    inline void ask(int x) {
        int p = 0;
        while (x)
            for (auto o : ch[p])
                if (x - cnt[o.se] > 0) x -= cnt[o.se];
                else {
                    putchar(o.fi), p = o.se, --x;
                    break;
                }
        putchar('\n');
    }
} sam;

int main() {
    rds(sam.s, sam.n), sam.build(), sam.sort();
    int q, x;
    rd(q);
    while (q--) rd(x), sam.ask(x);
    return 0;
}

【例题】SP1811 LCS – Longest Common Substring

两个串的最大公共子串。

对第一个串建 SAM,然后依次加入第二个串的字符,求当前第二个串的是第一个串的子串的最长后缀。

用一个指针记录当前解在 SAM 上的位置,加入一个字符时先看能不能匹配,如果能就直接匹配,不能就暴力跳 $\operatorname{parent}$,直到可以匹配为止。

每次的解取 $\max$ 即为最优解。

const int N = 2.5e5 + 7;
struct SAM {
    int n, l, len[N<<1], pa[N<<1], t;
    char s[N];
    map<char, int> ch[N<<1];
    inline void init() { pa[0] = -1; }
    inline void add(char c) {
        int w = ++t, p = l;
        len[w] = len[l] + 1;
        while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
        if (!~p) return pa[l=w] = 0, void();
        int q = ch[p][c];
        if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
        int k = ++t;
        pa[k] = pa[q], ch[k] = ch[q];
        len[k] = len[p] + 1, pa[w] = pa[q] = k;
        while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
        l = w;
    }
    inline void build() {
        init();
        for (int i = 1; i <= n; i++) add(s[i]);
    }

    int op, ol, ans;
    inline void calc(char c) {
        while (op && !ch[op][c]) op = pa[op], ol = len[op];
        if (ch[op][c]) op = ch[op][c], ++ol;
        ans = max(ans, ol);
    }
} sam;

char s[N];
int n;

int main() {
    rds(sam.s, sam.n), sam.build();
    rds(s, n);
    for (int i = 1; i <= n; i++) sam.calc(s[i]);
    print(sam.ans);
    return 0;
}

【例题】SP10570 LONGCS – Longest Common Substring

多个串的最大公共子串。

依然对第一个串建 SAM,类似两个串的情况,将其他串放到 SAM 上匹配。

维护 SAM 每个状态的最长匹配长度,每次的解取 $\min$,所有状态取 $\max$ 即可。

const int N = 1e4 + 7;
char s[N];
int n, ans[N<<1];
struct SAM {
    int n, l, ch[N<<1][26], len[N<<1], pa[N<<1], t;
    char s[N];
    inline void init() {
        for (int i = 0; i <= t; i++)
            memset(ch[i], 0, sizeof(ch[i]));
        t = l = len[0] = 0, pa[0] = -1;
    }
    inline void add(int c) {
        int w = ++t, p = l;
        len[w] = len[l] + 1;
        while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
        if (!~p) return pa[l=w] = 0, void();
        int q = ch[p][c];
        if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
        int k = ++t;
        pa[k] = pa[q], memcpy(ch[k], ch[q], sizeof(ch[k]));
        len[k] = len[p] + 1, pa[w] = pa[q] = k;
        while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
        l = w;
    }
    inline void build() {
        init();
        for (int i = 1; i <= n; i++) add(s[i] - 'a');
    }

    int b[N<<1], c[N];
    inline void sort() {
        for (int i = 1; i <= n; i++) c[i] = 0;
        for (int i = 1; i <= t; i++) ++c[len[i]];
        for (int i = 1; i <= n; i++) c[i] += c[i-1];
        for (int i = 1; i <= t; i++) b[c[len[i]]--] = i;
    }
    int op, ol, ans[N<<1];
    inline void calc(int c) {
        while (op && !ch[op][c]) op = pa[op], ol = len[op];
        if (ch[op][c]) op = ch[op][c], ++ol, ans[op] = max(ans[op], ol);
    }
    inline void update() {
        for (int i = t; i; i--) {
            int x = b[i];
            ans[pa[x]] = max(ans[pa[x]], min(ans[x], len[pa[x]]));
            ::ans[x] = min(::ans[x], ans[x]), ans[x] = 0;
        }
    }
} sam;

inline void solve() {
    int m;
    rd(m), rds(sam.s, sam.n), sam.build(), sam.sort();
    for (int i = 1; i <= sam.t; i++) ans[i] = 1e9;
    while (--m) {
        rds(s, n), sam.op = sam.ol = 0;
        for (int i = 1; i <= n; i++) sam.calc(s[i] - 'a');
        sam.update();
    }
    print(*max_element(ans + 1, ans + sam.t + 1));
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

参考资料

一条评论
  • suiqingying

    2020年3月26日 上午10:40

    很精致

发表评论

电子邮件地址不会被公开。 必填项已用*标注