深入理解后缀自动机（Suffix Automaton）

核心概念解析

• 状态（State）：每个状态代表字符串的一组 endpos 等价类（即所有具有相同结束位置集合的子串）。
• 转移（Transition）：从一个状态通过某个字符转移到另一个状态。
• 后缀链接（Suffix Link）：指向当前状态所代表子串的最长真后缀对应的状态，用于构建过程中的回溯。

用 Rust 实现后缀自动机

我们将逐步构建一个支持动态添加字符的后缀自动机。首先定义状态结构：

struct State {    len: usize,           // 当前状态代表的最长子串长度    link: i32,            // 后缀链接，-1 表示无    next: [i32; 26],       // 转移数组，假设只处理小写字母}impl State {    fn new(len: usize) -> Self {        State {            len,            link: -1,            next: [-1; 26],        }    }}  

接下来是后缀自动机主体结构：

struct SuffixAutomaton {    states: Vec<State>,    last: i32,}impl SuffixAutomaton {    fn new() -> Self {        let mut sa = SuffixAutomaton {            states: Vec::new(),            last: 0,        };        sa.states.push(State::new(0)); // 初始状态        sa    }    fn extend(&mut self, c: char) {        let cur = self.states.len() as i32;        self.states.push(State::new(self.states[self.last as usize].len + 1));                let idx = (c as u8 - b'a') as usize;        let mut p = self.last;                // 设置转移        while p != -1 && self.states[p as usize].next[idx] == -1 {            self.states[p as usize].next[idx] = cur;            p = self.states[p as usize].link;        }                if p == -1 {            self.states[cur as usize].link = 0;        } else {            let q = self.states[p as usize].next[idx];            if self.states[p as usize].len + 1 == self.states[q as usize].len {                self.states[cur as usize].link = q;            } else {                // 克隆状态                let clone = self.states.len() as i32;                self.states.push(self.states[q as usize].clone());                self.states[clone as usize].len = self.states[p as usize].len + 1;                                // 更新 q 和 cur 的后缀链接                while p != -1 && self.states[p as usize].next[idx] == q {                    self.states[p as usize].next[idx] = clone;                    p = self.states[p as usize].link;                }                self.states[q as usize].link = clone;                self.states[cur as usize].link = clone;            }        }        self.last = cur;    }}  

使用示例：统计不同子串数量

构建完自动机后，我们可以利用每个状态的 len 和 link 信息快速计算不同子串总数：

impl SuffixAutomaton {    fn count_distinct_substrings(&self) -> usize {        let mut total = 0;        for i in 1..self.states.len() {            total += self.states[i].len - self.states[self.states[i].link as usize].len;        }        total    }}// 测试fn main() {    let mut sa = SuffixAutomaton::new();    for c in "abcbc".chars() {        sa.extend(c);    }    println!("不同子串数量: {}", sa.count_distinct_substrings());    // 输出: 13}  

为什么选择 Rust 实现？

Rust 提供了内存安全、零成本抽象和高性能特性，非常适合实现如Rust后缀自动机这类对性能敏感的数据结构。其所有权系统还能帮助我们在编译期避免常见的内存错误。

总结

通过本教程，你已经掌握了后缀自动机的基本原理，并用Rust编程教程中推荐的方式亲手实现了它。这项技术广泛应用于文本编辑器、生物信息学、搜索引擎等领域。掌握它，你就拥有了处理大规模字符串问题的利器！

记住，字符串算法的核心在于理解状态转移与数学性质。多练习、多调试，你会越来越熟练。现在，尝试扩展这个实现以支持 Unicode 字符，或者用它解决最长公共子串问题吧！

关键词回顾：Rust后缀自动机、字符串算法、Rust编程教程、后缀自动机实现