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++免费学习笔记（深入）”；

构建后缀自动机

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

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 可以高效求解多种问题：

GPT Detector

在线检查文本是否由GPT-3或ChatGPT生成

下载

1. 不同子串个数

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