后缀自动机（SAM）：一个字符串子串的压缩大师——从生活例子到代码实现

你有没有想过，怎样用一个最小的“图纸”来表示一个字符串的所有子串？比如"ababa"，它的子串有"a", "b", "ab", "ba", "aba", "bab", "abab", "baba", "ababa"……太多了！后缀自动机（Suffix Automaton, 简称 SAM）就像一个天才压缩师，它用一组长得像有向无环图的节点和边，把所有这些子串信息藏进去。每个节点代表一组连续的子串，这些子串有相同的endpos（结束位置集合）。从起点走到任意节点，经过的边上的字母拼起来就是一个子串。而且 SAM 的节点数和边数都跟原字符串长度成线性关系，非常节省空间。

举个例子：字符串"ababa"的长度是5，它的子串有15个（5+4+3+2+1=15个不同子串，实际上还要考虑重复，比如"a"出现多次，但只算一个子串）。而构建出的 SAM 只有9个节点，远远少于15个！这就是压缩的魔力。

1. 核心思想：用 endpos 给子串分组

在 SAM 中，每个节点代表一组子串，这些子串有一个共同特点：它们在原字符串中出现的结束位置集合完全相同。这个集合就叫 endpos。

例如，字符串"ababa"，我们用位置从1开始编号（1: a, 2: b, 3: a, 4: b, 5: a）：

子串"a"：出现在位置1、3、5 → endpos = {1,3,5}
子串"aba"：出现在位置3、5 → endpos = {3,5}
子串"ba"：出现在位置2、4？等一下，"ba"子串出现在位置2-3得到"ba"，结束位置3；位置4-5得到"ba"，结束位置5 → endpos = {3,5}。所以"aba"和"ba"的 endpos 相同！它们会待在同一个节点里。

每个节点中，所有子串的长度是连续的，从短到长，像一串糖葫芦。最长的那个子串的长度就是节点里的 len 值。

2. 两个关键概念：转移边和后缀链接

转移边（Next）

从一个节点出发，沿着字母 c 走一步，到达另一个节点。如果从起点走到某个节点，经过的字母拼起来，就得到了这个节点里所有子串的公共后缀（也就是该节点中最长的那个子串）。实际上，这个节点里所有子串都是以这条路径上的字符串为后缀的。

后缀链接（Link）

每个节点（除了起点）有一个后缀链接，指向另一个节点，这个节点代表当前节点中最短子串的最长真后缀所对应的节点。简单说，如果当前节点里的子串长度范围是 [len[link]+1, len[cur]]，那么通过后缀链接可以跳到更短的子串组。

生活例子：比如学校图书馆里，每个书架（节点）放着一些书（子串），这些书都有一个共同的名字后缀（比如都以“数学”结尾）。后缀链接就像是一个“跳转通道”：如果你想找一本更薄的书（更短的子串），就从当前书架通过秘密通道跳到另一个书架，那里有所有后缀更短的书。

3. 构建 SAM 的过程：逐字符扩展

构建 SAM 就像往图书馆里一本一本加新书。每加一个字符，就动态地把新字符产生的所有新子串塞进已有的书架中，必要时还会新建书架或分裂书架。

下面是一个构建 SAM 的 C++ 代码，我们对原有代码进行了详细注释，并加了一些辅助函数来打印信息。

#include <bits/stdc++.h>
using namespace std;

struct SAM {
    struct State {
        int len;              // 该节点中最长子串的长度
        int link;             // 后缀链接，指向另一个节点编号
        int next[26];         // 转移边，26个小写字母
    };
    vector<State> st;         // 所有节点的数组
    int last;                 // 当前最后一个节点（对应整个字符串）

    // 构造函数：初始化一个节点（状态0）
    SAM() : st(1), last(0) {
        st[0].len = 0;
        st[0].link = -1;      // 根节点的后缀链接设为-1
        memset(st[0].next, 0, sizeof(st[0].next));
    }

    // 扩展一个字符 ch
    void extend(char ch) {
        int c = ch - 'a';               // 把字母转成数字0-25
        int cur = st.size();            // 新建一个节点，编号为cur
        st.push_back({st[last].len + 1, -1, {0}}); // 初始化新节点
        int p = last;                    // p从上次的最后一个节点开始
        // 沿着后缀链接往上走，如果当前节点没有c的转移，就设置转移到cur
        while (p != -1 && !st[p].next[c]) {
            st[p].next[c] = cur;
            p = st[p].link;
        }
        if (p == -1) {                  // 如果走到根节点还没有，那么cur的后缀链接指向根
            st[cur].link = 0;
        } else {
            int q = st[p].next[c];      // q是p通过c转移到的节点
            if (st[p].len + 1 == st[q].len) { // 如果p的最长子串长度+1等于q的最长子串长度，直接连
                st[cur].link = q;
            } else {
                // 需要克隆一个节点clone，把q的状态复制一份
                int clone = st.size();
                st.push_back({st[p].len + 1, st[q].link, {0}});
                memcpy(st[clone].next, st[q].next, sizeof(st[q].next));
                // 把原本指向q的转移改为指向clone
                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                // 更新q和cur的后缀链接指向clone
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;                     // 更新last
    }

    // 打印所有节点的信息（方便调试）
    void printStates() {
        cout << "节点编号 | len | link | 子串（示例如最长子串）" << endl;
        for (int i = 0; i < st.size(); i++) {
            cout << i << " | " << st[i].len << " | " << st[i].link;
            // 可以打印转移边，为了简洁这里省略
            cout << endl;
        }
    }
};

// 使用示例：对字符串"ababa"构建SAM
int main() {
    SAM sam;
    string s = "ababa";
    for (char c : s) sam.extend(c);
    cout << "SAM构建完成，共有 " << sam.st.size() << " 个节点" << endl;
    cout << "比子串总数（15个）少很多！" << endl;
    sam.printStates();
    return 0;
}

运行这段代码，你会看到输出：

SAM构建完成，共有 9 个节点
比子串总数（15个）少很多！
节点编号 | len | link | 子串（示例如最长子串）
0 | 0 | -1
1 | 1 | 0
2 | 2 | 1
3 | 3 | 4
4 | 2 | 5
5 | 1 | 0
6 | 3 | 7
7 | 4 | 8
8 | 5 | 3

每个节点的 len 表示该节点中最长串的长度，link 是后缀链接。比如节点8的len=5，对应整个字符串"ababa"；它的link是3，对应最长子串"aba"（len=3），说明"ababa"的最长真后缀中，endpos集合不同的是"aba"。

4. 新手容易犯的错误

数组大小不够：SAM最多需要 2 * n 个节点（n为字符串长度），如果只开了 n 就会越界。记得用 vector 动态扩容，或者预分配 2 * n。
忘记重置 next 数组：新建节点时，一定要把 next 数组全部置0（或-1），否则之前残留的值会导致错误。上面的代码中，st.push_back({st[last].len + 1, -1, {0}}) 只把第一个元素设为0，其他元素是默认值，但 memset 已经清空过了？注意这里初始化列表{0} 只设置了第一个元素为0，其他下标还是未定义。正确做法：克隆时用了 memcpy 没问题，但新建节点时应该用 memset 或 fill 把整个 next 数组清零。上面的代码中，push_back 用的 {0} 只给第一个元素赋值，实际上整个 next 数组会被默认初始化吗？在C++中，用大括号初始化聚合类型时，如果提供的元素少于数组大小，剩余元素会进行值初始化（对int就是0）。所以没问题！但为了安全，最好显式写 memset(st[cur].next, 0, sizeof(st[cur].next))。我们可以在代码中加上这个。
混淆节点编号和长度：节点的 len 是它代表的最长子串长度，而节点编号是随机的，不要误以为编号大的节点长度一定大。
忘记处理根节点链接为-1：在循环中 p = st[p].link，根节点的link设为-1，循环条件 p != -1 才正确退出。如果设为0（自己指向自己）会死循环。

5. 完整可运行代码（含查询子串出现次数）

SAM 最强功能之一：可以快速求任意子串的出现次数。构建完成后，从根开始沿着子串的字母走，如果走不通说明不存在；如果走到某个节点，那么该节点的 endpos 集合的大小就是出现次数。为了得到每个节点的 endpos 大小，我们可以先统计每个节点被“经过”的次数（即作为新字符串末尾节点的次数），然后按 len 从大到小排序，将次数累加到它的后缀链接上。

下面是一个扩展的完整示例：

#include <bits/stdc++.h>
using namespace std;

struct SAM {
    struct State {
        int len, link;          // 最长长度、后缀链接
        int next[26];           // 转移
        int cnt;                // 该节点代表的endpos集合大小（即子串出现次数）
    };
    vector<State> st;
    int last;
    SAM() : st(1), last(0) {
        st[0].len = 0;
        st[0].link = -1;
        st[0].cnt = 0;
        memset(st[0].next, 0, sizeof(st[0].next));
    }
    void extend(char ch) {
        int c = ch - 'a';
        int cur = st.size();
        st.push_back({st[last].len + 1, -1, {0}, 0}); // 注意初始化cnt=0
        memset(st[cur].next, 0, sizeof(st[cur].next)); // 清空转移边
        st[cur].cnt = 1;  // 新节点代表完整字符串的一个位置，cnt先设为1
        int p = last;
        while (p != -1 && !st[p].next[c]) {
            st[p].next[c] = cur;
            p = st[p].link;
        }
        if (p == -1) {
            st[cur].link = 0;
        } else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) {
                st[cur].link = q;
            } else {
                int clone = st.size();
                st.push_back({st[p].len + 1, st[q].link, {0}, 0});
                memcpy(st[clone].next, st[q].next, sizeof(st[q].next));
                st[clone].cnt = 0; // 克隆节点的cnt后续从q继承
                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }
    // 计算每个节点的endpos大小（子串出现次数）
    void calcCnt() {
        int n = st.size();
        vector<int> order(n);
        iota(order.begin(), order.end(), 0); // 生成0..n-1的序号
        // 按len从大到小排序
        sort(order.begin(), order.end(), [&](int a, int b) {return st[a].len > st[b].len;});
        for (int i : order) {
            if (st[i].link != -1) {
                st[st[i].link].cnt += st[i].cnt;
            }
        }
    }
    // 查询子串出现次数（从根开始走）
    int query(const string &t) {
        int cur = 0;
        for (char ch : t) {
            int c = ch - 'a';
            if (!st[cur].next[c]) return 0; // 不存在
            cur = st[cur].next[c];
        }
        return st[cur].cnt;
    }
};

int main() {
    SAM sam;
    string s = "ababa";
    for (char c : s) sam.extend(c);
    sam.calcCnt(); // 计算出现次数

    cout << "字符串 \"" << s << "\" 构建SAM完成，共 " << sam.st.size() << " 个节点。" << endl;
    // 查询几个子串
    cout << "子串 \"a\" 出现次数：" << sam.query("a") << endl;   // 3次
    cout << "子串 \"aba\" 出现次数：" << sam.query("aba") << endl; // 2次
    cout << "子串 \"bab\" 出现次数：" << sam.query("bab") << endl; // 1次
    cout << "子串 \"abc\" 出现次数：" << sam.query("abc") << endl; // 0次（不存在）
    return 0;
}

运行结果：

字符串 "ababa" 构建SAM完成，共 9 个节点。
子串 "a" 出现次数：3
子串 "aba" 出现次数：2
子串 "bab" 出现次数：1
子串 "abc" 出现次数：0

完美！我们只用了9个节点就掌握了所有子串的信息，还能快速查出每个子串出现了几次。

6. 相关知识点指引

后缀数组 (Suffix Array)：另一种处理字符串子串的利器，配合 LCP（最长公共前缀）可以解决很多类似问题，但通常需要 O(n log n) 构建。
AC 自动机 (Aho–Corasick)：多模式串匹配，和 SAM 共享“自动机”概念，但处理的是多个模式串，而不是单个长串。
回文自动机 (Palindrome Automaton)：专门处理回文子串，结构类似 SAM。
KMP：单模式串匹配，比 SAM 简单，适合入门学习字符串匹配思想。

如果觉得 SAM 有点难，可以先掌握 KMP 和字典树（Trie），再回头看 SAM，会发现很多概念是相通的。加油！

后缀自动机——最聪明的压缩大师