Rust语言实现AC自动机（高效多模式字符串匹配算法详解）

什么是AC自动机？

AC自动机是一种用于多模式字符串匹配的高效算法。它结合了 Trie树（前缀树）和 KMP算法 的思想，能够在一次扫描中同时匹配多个模式串。

它的核心优势在于：时间复杂度为 O(n + m + z)，其中 n 是文本长度，m 是所有模式串总长度，z 是匹配结果数量。这比对每个模式单独做 KMP 要快得多。

AC自动机的三个关键步骤

1. 构建 Trie 树：将所有模式串插入到一棵前缀树中。
2. 构建失败指针（Failure Link）：类似 KMP 的 next 数组，用于在匹配失败时跳转。
3. 匹配文本：利用 Trie 和失败指针，在文本中高效查找所有模式。

用Rust实现AC自动机

我们将逐步实现一个支持添加模式、构建自动机、匹配文本的结构体。首先，定义节点结构：

#[derive(Default)]pub struct Node {    children: [Option<usize>; 26], // 假设只处理小写字母 a-z    fail: usize,    output: Vec<String>, // 存储以该节点结尾的模式串}

接下来，定义 AC 自动机主结构：

pub struct AhoCorasick {    trie: Vec<Node>,    built: bool,}impl AhoCorasick {    pub fn new() -> Self {        let mut trie = Vec::new();        trie.push(Node::default()); // 根节点，索引为0        Self { trie, built: false }    }    // 添加一个模式串    pub fn add_pattern(&mut self, pattern: &str) {        if self.built {            panic!("Cannot add patterns after building the automaton!");        }        let mut node = 0;        for ch in pattern.chars() {            let idx = (ch as u8 - b'a') as usize;            if self.trie[node].children[idx].is_none() {                self.trie.push(Node::default());                self.trie[node].children[idx] = Some(self.trie.len() - 1);            }            node = self.trie[node].children[idx].unwrap();        }        self.trie[node].output.push(pattern.to_string());    }}

构建失败指针

使用 BFS（广度优先搜索）来设置失败指针：

use std::collections::VecDeque;impl AhoCorasick {    pub fn build(&mut self) {        let mut queue = VecDeque::new();        // 初始化：根的所有子节点的 fail 指向根        for i in 0..26 {            if let Some(child) = self.trie[0].children[i] {                self.trie[child].fail = 0;                queue.push_back(child);            }        }        while let Some(node_idx) = queue.pop_front() {            let fail_to = self.trie[node_idx].fail;            for i in 0..26 {                if let Some(child) = self.trie[node_idx].children[i] {                    // 找到当前节点的 fail 节点对应的子节点                    let mut f = fail_to;                    while f != 0 && self.trie[f].children[i].is_none() {                        f = self.trie[f].fail;                    }                    self.trie[child].fail =                         self.trie[f].children[i].unwrap_or(0);                                        // 合并输出：将 fail 路径上的输出也加入当前节点                    let fail_output = self.trie[self.trie[child].fail].output.clone();                    self.trie[child].output.extend(fail_output);                                        queue.push_back(child);                }            }        }        self.built = true;    }}

执行匹配

现在我们可以扫描文本并返回所有匹配结果：

pub struct Match {    pub pattern: String,    pub start: usize,    pub end: usize,}impl AhoCorasick {    pub fn find_matches(&self, text: &str) -> Vec<Match> {        assert!(self.built, "Automaton must be built before matching!");        let mut matches = Vec::new();        let mut node = 0;        for (i, ch) in text.chars().enumerate() {            if !ch.is_ascii_lowercase() {                // 遇到非小写字母，重置到根                node = 0;                continue;            }            let idx = (ch as u8 - b'a') as usize;            // 沿着 fail 指针回退，直到找到匹配或回到根            while node != 0 && self.trie[node].children[idx].is_none() {                node = self.trie[node].fail;            }            if let Some(next) = self.trie[node].children[idx] {                node = next;                // 报告所有在该位置结束的模式                for pattern in &self.trie[node].output {                    let start = i + 1 - pattern.len();                    matches.push(Match {                        pattern: pattern.clone(),                        start,                        end: i + 1,                    });                }            }        }        matches    }}

完整使用示例

fn main() {    let mut ac = AhoCorasick::new();    ac.add_pattern("he");    ac.add_pattern("she");    ac.add_pattern("his");    ac.add_pattern("hers");    ac.build();    let text = "ushers";    let matches = ac.find_matches(text);    for m in &matches {        println!("Found '{}' at [{}..{})", m.pattern, m.start, m.end);    }    // 输出：    // Found 'she' at [1..4)    // Found 'he' at [2..4)    // Found 'hers' at [2..6)}

总结

通过本教程，你已经学会了如何用 Rust 从零实现一个功能完整的 AC自动机。这项技术在实际工程中非常有用，比如实现高性能的关键词过滤系统、日志分析工具等。

记住，AC自动机的核心是：Trie树 + 失败指针 + BFS构建。掌握这三点，你就掌握了多模式匹配的利器。

希望这篇关于 Rust AC自动机、Rust字符串匹配、AC自动机算法实现 和 Rust多模式匹配 的教程对你有帮助！你可以在此基础上扩展支持 Unicode、大小写不敏感、通配符等功能。