高效字符串匹配利器：Rust后缀数组详解（从零实现后缀数组算法）

为什么使用 Rust 实现后缀数组？

Rust 是一门内存安全、高性能的系统编程语言。使用 Rust 实现Rust算法实现不仅能获得接近 C/C++ 的性能，还能避免常见的内存错误。对于需要处理大量文本数据的应用（如搜索引擎、DNA 序列分析），Rust 后缀数组是一个理想选择。

基础版本：暴力构建后缀数组

我们先从最直观的方法开始——生成所有后缀，然后排序。虽然时间复杂度为 O(n² log n)，但对于理解概念非常有帮助。

use std::cmp::Ordering;fn build_suffix_array_naive(s: &str) -> Vec<usize> {    let n = s.len();    let chars: Vec<char> = s.chars().collect();    let mut suffixes: Vec<(Vec<char>, usize)> = Vec::with_capacity(n);    // 生成所有后缀    for i in 0..n {        let suffix: Vec<char> = chars[i..].to_vec();        suffixes.push((suffix, i));    }    // 按字典序排序    suffixes.sort_by(|a, b| a.0.cmp(&b.0));    // 提取起始索引    suffixes.into_iter().map(|(_, idx)| idx).collect()}fn main() {    let text = "banana";    let sa = build_suffix_array_naive(text);    println!("后缀数组: {:?}", sa); // 输出: [5, 3, 1, 0, 4, 2]}

这段代码清晰地展示了后缀数组的构建过程。但请注意，它在处理长字符串时效率较低。

优化版本：使用倍增法（O(n log n)）

为了提升性能，我们可以使用倍增法（Doubling Algorithm）。该方法通过逐步比较长度为 1、2、4、8... 的子串来排序后缀。

fn build_suffix_array_optimized(s: &str) -> Vec<usize> {    let n = s.len();    let chars: Vec<u8> = s.bytes().collect();    let mut sa: Vec<usize> = (0..n).collect();    let mut rank = vec![0; n];    let mut new_rank = vec![0; n];    // 初始排序：按单个字符    sa.sort_by_key(|&i| chars[i]);    // 初始化 rank    rank[sa[0]] = 0;    for i in 1..n {        rank[sa[i]] = rank[sa[i - 1]] +             if chars[sa[i]] == chars[sa[i - 1]] { 0 } else { 1 };    }    let mut k = 1;    while k < n {        // 按第二关键字排序（即 i + k 的 rank）        sa.sort_by(|&a, &b| {            let second_a = if a + k < n { rank[a + k] } else { -1 };            let second_b = if b + k < n { rank[b + k] } else { -1 };            (rank[a], second_a).cmp(&(rank[b], second_b))        });        // 重新计算 rank        new_rank[sa[0]] = 0;        for i in 1..n {            let prev = (                rank[sa[i - 1]],                if sa[i - 1] + k < n { rank[sa[i - 1] + k] } else { -1 }            );            let curr = (                rank[sa[i]],                if sa[i] + k < n { rank[sa[i] + k] } else { -1 }            );            new_rank[sa[i]] = new_rank[sa[i - 1]] + if prev == curr { 0 } else { 1 };        }        rank.copy_from_slice(&new_rank);        if rank[sa[n - 1]] == n as i32 - 1 {            break; // 所有后缀已唯一排序        }        k *= 2;    }    sa}

这个版本的时间复杂度为 O(n log n)，适用于大多数实际场景。注意：为了简化，这里使用了 i32 表示 rank，实际项目中建议使用更安全的类型。

应用场景与总结

掌握Rust后缀数组后，你可以将其用于：

• 快速查找子字符串（配合二分搜索）
• 寻找最长公共前缀（LCP）
• 基因序列比对
• 文本压缩（如 Burrows-Wheeler 变换）

通过本教程，你不仅学会了如何用 Rust 构建后缀数组，还理解了其背后的算法思想。无论是进行Rust字符串处理还是深入研究Rust算法实现，后缀数组都是一个值得掌握的工具。

希望这篇关于后缀数组算法的教程对你有所帮助！动手试试吧，你会发现 Rust 在算法实现上的优雅与高效。