C++怎么实现一个后缀自动机(SAM)_C++高级字符串算法与子串问题-C++-PHP中文网

C++怎么实现一个后缀自动机(SAM)_C++高级字符串算法与子串问题

裘德小鎮的故事

发布： 2025-12-09 17:28:02

原创

299人浏览过

后缀自动机能在线性时间内构建并解决子串相关问题，其核心是通过状态转移和后缀链接表示所有子串。

c++怎么实现一个后缀自动机(sam)_c++高级字符串算法与子串问题

后缀自动机（Suffix Automaton，简称 SAM）是处理字符串子串问题的高效数据结构。它能在 O(n) 时间内构建，并支持快速解决子串计数、最长公共子串、不同子串个数等问题。下面介绍 C++ 中如何实现一个基础的后缀自动机。

什么是后缀自动机

后缀自动机是一个有向图，其中每个节点代表原字符串某个子串的“状态”，边表示在该状态后添加一个字符能转移到的新状态。SAM 的核心性质包括：

所有从初始状态可达的路径，对应原串的所有子串。
总状态数不超过 2n，转移边数不超过 3n。
每个状态记录了该状态所代表子串的最长长度（len）和最小长度（通过 link 树推导）。

核心结构与变量定义

我们用结构体维护 SAM 的每个节点，主要包含以下字段：

len：当前状态能表示的最长子串长度。
link：后缀链接（suffix link），指向另一个状态，表示当前状态的最长串的真后缀中最长的可接受状态。
next[26]：转移数组，记录添加字符 a~z 后的下一个状态。

// 假设只处理小写字母 struct State { int len; // 最长子串长度 int link; // 后缀链接 int next[26]; // 转移边 State() { len = 0; link = -1; for (int i = 0; i

全局维护一个状态数组和相关变量：

立即学习“C++免费学习笔记（深入）”；

vector st; int last = 0; // 当前最后一个字符所在的状态 int sz = 0; // 状态总数

构建后缀自动机

每次添加一个字符时，创建新状态并更新后缀链接。算法核心步骤如下：

void sam_init() { st.push_back(State()); sz++; last = 0; }

void sam_extend(char c) { int cur = sz++; st.push_back(State()); st[cur].len = st[last].len + 1; int p = last;

// 从 last 开始，沿着后缀链接走，直到根或已有 c 转移
while (p != -1 && st[p].next[c - 'a'] == -1) {
    st[p].next[c - 'a'] = cur;
    p = st[p].link;
}

if (p == -1) {
    st[cur].link = 0;
} else {
    int q = st[p].next[c - 'a'];
    if (st[p].len + 1 == st[q].len) {
        st[cur].link = q;
    } else {
        int clone = sz++;
        st.push_back(st[q]);  // 复制 q 的信息
        st[clone].len = st[p].len + 1;
        // 将 q 的转移复制，但不改变 len 和 link

        while (p != -1 && st[p].next[c - 'a'] == q) {
            st[p].next[c - 'a'] = clone;
            p = st[p].link;
        }
        st[q].link = st[cur].link = clone;
    }
}
last = cur;

登录后复制

}

说明：

每次扩展字符 c，新建状态 cur，其最长长度为 last.len + 1。
从 last 沿着 link 往上跳，为没有 c 转移的状态添加指向 cur 的边。
若遇到已有 c 转移的状态 p，则检查目标状态 q 是否满足 len 条件。
若不满足（即 q 是被多个路径共享的复杂状态），则需分裂出一个 clone 状态来保证正确性。

常见应用示例

利用 SAM 可以高效求解多种问题：

面多多

面试鸭推出的AI面试训练平台

219

查看详情

1. 不同子串个数

每个状态表示若干长度连续的子串，数量为 len - len(link)。累加所有状态即可。

long long count_distinct_substrings() { long long total = 0; for (int i = 1; i

2. 最短未出现子串

从初始状态开始 BFS，找第一个缺失的字符转移，该字符即是最短未出现子串。

3. 最长公共子串（两个串）

对第一个串建 SAM，然后用第二个串在 SAM 上匹配，维护当前匹配长度和状态，不断沿 link 跳转以缩短匹配。

int longest_common_substring(string s, string t) { int res = 0, v = 0, l = 0; for (char c : t) { while (v && st[v].next[c-'a'] == -1) { v = st[v].link; l = st[v].len; } if (st[v].next[c-'a'] != -1) { v = st[v].next[c-'a']; l++; } res = max(res, l); } return res; }

基本上就这些。SAM 虽初看复杂，但掌握 extend 过程和 link 作用后，理解会清晰很多。关键是理解 clone 操作的意义：保持 DAG 中每个状态的 right 集合一致。

以上就是C++怎么实现一个后缀自动机(SAM)_C++高级字符串算法与子串问题的详细内容，更多请关注php中文网其它相关文章！