Rust后缀数组实现（从零开始构建高效文本搜索结构）

为什么选择 Rust 实现？

Rust 是一门内存安全、高性能的系统级编程语言。使用 Rust 实现 Rust后缀数组实现 不仅能保证运行效率，还能避免常见的内存错误。同时，Rust 的类型系统和所有权机制让代码更健壮，非常适合学习算法与数据结构。

步骤一：定义基本结构

我们首先创建一个 SuffixArray 结构体，用于保存原始字符串和后缀数组。

struct SuffixArray {    text: String,    suffixes: Vec<usize>,}

步骤二：构建后缀数组（O(n² log n) 方法）

对于初学者，我们先使用一种简单但效率较低的方法：生成所有后缀，然后排序。虽然这不是最优解（最优为 O(n) 的 SA-IS 算法），但逻辑清晰，便于理解。

impl SuffixArray {    fn new(s: &str) -> Self {        let mut indices: Vec<usize> = (0..s.len()).collect();                // 按后缀的字典序对索引排序        indices.sort_by(|&a, &b| {            let suffix_a = &s[a..];            let suffix_b = &s[b..];            suffix_a.cmp(suffix_b)        });        SuffixArray {            text: s.to_string(),            suffixes: indices,        }    }}

步骤三：添加查询功能

构建完成后，我们可以添加方法来打印后缀数组，或用于后续的 高效文本搜索。

impl SuffixArray {    fn print_suffixes(&self) {        println!("Suffix Array for: {}", self.text);        for &idx in &self.suffixes {            println!("{}: {}", idx, &self.text[idx..]);        }    }}

完整示例代码

下面是完整的可运行代码，你可以复制到你的 Rust 项目中测试。

fn main() {    let sa = SuffixArray::new("banana");    sa.print_suffixes();}struct SuffixArray {    text: String,    suffixes: Vec<usize>,}impl SuffixArray {    fn new(s: &str) -> Self {        let mut indices: Vec<usize> = (0..s.len()).collect();        indices.sort_by(|&a, &b| {            let suffix_a = &s[a..];            let suffix_b = &s[b..];            suffix_a.cmp(suffix_b)        });        SuffixArray {            text: s.to_string(),            suffixes: indices,        }    }    fn print_suffixes(&self) {        println!("Suffix Array for: {}", self.text);        for &idx in &self.suffixes {            println!("{}: {}", idx, &self.text[idx..]);        }    }}

运行结果

运行上述代码，你将看到如下输出：

Suffix Array for: banana5: a3: ana1: anana0: banana4: na2: nana

进阶优化方向

上述实现的时间复杂度为 O(n² log n)，因为每次比较两个后缀可能需要 O(n) 时间。在实际应用中，可以采用以下优化：

• 使用 倍增算法（Doubling Algorithm）将复杂度降至 O(n log n)
• 使用 SA-IS 算法 实现 O(n) 构建
• 结合 LCP 数组（最长公共前缀）加速子串匹配

总结

通过本教程，你已经掌握了如何在 Rust 中实现一个基础的后缀数组。这不仅帮助你理解了 后缀数组算法 的核心思想，也为后续学习更高级的 Rust字符串处理 技术打下了基础。无论是用于面试准备还是实际项目开发，这项技能都非常实用。

如果你想进一步提升性能，建议研究 O(n log n) 的倍增法实现。但在大多数教学和小型应用场景中，本文的方法已经足够高效且易于理解。

关键词回顾：Rust后缀数组实现、后缀数组算法、Rust字符串处理、高效文本搜索。