后缀自动机 (Suffix Automaton) 模板详解

靖2025-01-072025-01-07

后缀自动机 (Suffix Automaton) 模板详解

1. 简介

后缀自动机（SAM）是一个强大的字符串处理工具，它可以在线性时间内处理字符串的所有子串信息。这是目前已知的最强大的字符串数据结构之一。

主要特点：

线性时间和空间复杂度
可以处理所有子串信息
支持在线构建
可以解决多种字符串问题

2. 实现原理

2.1 基本概念

状态：
- 每个状态代表一个子串集合
- 具有相同 right 集合的子串归为一类
后缀链接：
- 连接到最长的后缀状态
- 形成一个树形结构

2.2 核心策略

状态转移：
- 通过 next 数组记录转移
- 保持自动机的最小性
状态分裂：
- 在需要时创建新状态
- 维护后缀链接的正确性

3. 模板代码

struct SAM {
    static constexpr int ALPHABET_SIZE = 26;
    struct Node {
        int len;
        int link;
        std::array<int, ALPHABET_SIZE> next;
        Node() : len{}, link{}, next{} {}
    };
    std::vector<Node> t;
    SAM() {
        init();
    }
    void init() {
        t.assign(2, Node());
        t[0].next.fill(1);
        t[0].len = -1;
    }
    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }
    int extend(int p, int c) {
        if (t[p].next[c]) {
            int q = t[p].next[c];
            if (t[q].len == t[p].len + 1) {
                return q;
            }
            int r = newNode();
            t[r].len = t[p].len + 1;
            t[r].link = t[q].link;
            t[r].next = t[q].next;
            t[q].link = r;
            while (t[p].next[c] == q) {
                t[p].next[c] = r;
                p = t[p].link;
            }
            return r;
        }
        int cur = newNode();
        t[cur].len = t[p].len + 1;
        while (!t[p].next[c]) {
            t[p].next[c] = cur;
            p = t[p].link;
        }
        t[cur].link = extend(p, c);
        return cur;
    }
    int extend(int p, char c, char offset = 'a') {
        return extend(p, c - offset);
    }
    
    int next(int p, int x) {
        return t[p].next[x];
    }
    
    int next(int p, char c, char offset = 'a') {
        return next(p, c - 'a');
    }
    
    int link(int p) {
        return t[p].link;
    }
    
    int len(int p) {
        return t[p].len;
    }
    
    int size() {
        return t.size();
    }
};

4. 函数说明

4.1 结构体说明

struct Node {
    int len;    // 状态最长子串长度
    int link;   // 后缀链接
    std::array<int, ALPHABET_SIZE> next;  // 转移数组
};

4.2 主要函数

init(): 初始化自动机
extend(): 添加字符并更新状态
next(): 获取转移状态
link(): 获取后缀链接
len(): 获取状态长度

5. 时间复杂度分析

构建：O(n)
空间复杂度：O(n)
查询子串：O(m)，m为查询串长度

6. 应用场景

子串查找
最长公共子串
子串出现次数统计
字符串压缩

7. 使用示例

7.1 构建后缀自动机

SAM sam;
string s = "abcbc";
int v = 1;
for (char c : s) {
    v = sam.extend(v, c);
}

7.2 子串查找

bool findSubstring(const string& pattern) {
    int v = 1;
    for (char c : pattern) {
        v = sam.next(v, c);
        if (!v) return false;
    }
    return true;
}