AC 自动机（Aho-Corasick Automaton）详解
AC 自动机（Aho-Corasick Automaton）是一种高效的多模式字符串匹配算法，由 Alfred Aho 和 Margaret Corasick 在 1975 年提出。它结合了 Trie 树 和 KMP 算法 的思想，能够在 O(n + m + z) 的时间复杂度内完成多模式匹配，其中：
n是主串的长度，m是所有模式串的总长度，z是匹配成功的次数。
AC 自动机特别适合 多模式串匹配 场景，例如：
- 病毒扫描（检测文本中是否包含已知病毒特征码），
- 关键词过滤（如敏感词检测），
- DNA 序列分析等。
一、AC 自动机的核心思想
AC 自动机的核心思想是：
- Trie 树：将所有模式串构建成一棵 Trie 树，便于快速查找。
- 失败指针（Fail Pointer）：类似于 KMP 算法的
next数组，用于在不匹配时跳转，避免从头开始匹配。 - 输出函数（Output Function）：记录每个节点对应的匹配模式串。
二、AC 自动机的构建步骤
- 构建 Trie 树
将所有模式串插入到 Trie 树中，并为每个节点标记是否为某个模式串的结尾。
示例：
模式串集合：["he", "she", "his", "hers"]
构建的 Trie 树如下：
(root)
/ | \
h s ...
/ \ \
e i h
/ \ \
* s i
\ \
* r
\
s
*
其中 * 表示该节点是某个模式串的结尾。
- 构建失败指针（Fail Pointer）
失败指针的作用是：当当前字符匹配失败时，跳转到另一个节点继续匹配，类似于 KMP 的next数组。
构建规则：
- 根节点的失败指针：指向
null（或自身）。 - 根节点的子节点的失败指针：指向根节点（因为如果匹配失败，可以重新从根节点开始匹配）。
- 其他节点的失败指针： • 如果当前节点的父节点的失败指针有相同字符的子节点，则直接指向该子节点。 • 否则，继续沿着失败指针向上查找，直到找到匹配的子节点或回到根节点。
示例：
以 "he", "she", "his", "hers" 为例：
h的失败指针指向根节点（因为它是根节点的子节点）。e的失败指针：h的失败指针是根节点，根节点没有e子节点，所以e的失败指针指向根节点。s的失败指针：h的失败指针是根节点，根节点有s子节点，所以s的失败指针指向根节点的s子节点。i的失败指针：h的失败指针是根节点，根节点没有i子节点，所以i的失败指针指向根节点。r的失败指针：s的失败指针是h的s子节点，h的s子节点没有r子节点，继续向上找h的失败指针（根节点），根节点没有r子节点，所以r的失败指针指向根节点。
- 构建输出函数（Output Function）
输出函数用于记录每个节点对应的匹配模式串。如果某个节点是某个模式串的结尾，或者它的失败指针指向的节点是某个模式串的结尾，则该节点需要输出对应的模式串。
示例：
e是"he"的结尾，所以e的输出是"he"。s是"she"和"hers"的结尾，所以s的输出是"she"和"hers"（需要检查失败指针链）。
三、AC 自动机的匹配过程
- 初始化：从 Trie 树的根节点开始，逐个字符匹配主串。
- 匹配字符：
• 如果当前字符匹配成功，则移动到对应的子节点，并检查该节点及其失败指针链是否有输出。 • 如果匹配失败，则沿着失败指针跳转，直到找到匹配的子节点或回到根节点。 - 输出匹配结果：每当到达一个节点时，检查该节点及其失败指针链是否有输出，如果有则记录匹配的模式串。
示例：
主串："ahishers"
模式串集合：["he", "she", "his", "hers"]
匹配过程：
'a'：不匹配，停留在根节点。'h'：匹配，移动到h节点。'i'：匹配，移动到i节点（"his"匹配成功）。's'：匹配，移动到s节点（"his"和"hers"匹配成功）。
• 检查s的输出："hers"。 • 检查s的失败指针（指向h的s子节点）的输出："she"（因为h的s子节点是"she"的结尾）。'h'：不匹配，沿着s的失败指针跳转（回到h的s子节点的失败指针，即h节点）。'e'：匹配，移动到e节点（"he"匹配成功）。
最终匹配结果："his", "hers", "he"。
四、AC 自动机的 C++ 实现
以下是 AC 自动机的完整 C++ 实现：
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
struct TrieNode {
unordered_map<char, TrieNode*> children;
TrieNode* fail = nullptr;
vector<int> output; // 存储匹配的模式串索引
};
class ACAutomaton {
private:
TrieNode* root;
vector<string> patterns;
void buildTrie(const vector<string>& patterns) {
this->patterns = patterns;
root = new TrieNode();
for (int i = 0; i < patterns.size(); ++i) {
TrieNode* node = root;
for (char c : patterns[i]) {
if (!node->children.count(c)) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->output.push_back(i); // 记录模式串索引
}
}
void buildFailPointers() {
queue<TrieNode*> q;
root->fail = nullptr;
for (auto& [c, child] : root->children) {
child->fail = root;
q.push(child);
}
while (!q.empty()) {
TrieNode* current = q.front();
q.pop();
for (auto& [c, child] : current->children) {
TrieNode* failNode = current->fail;
while (failNode != nullptr && !failNode->children.count(c)) {
failNode = failNode->fail;
}
child->fail = (failNode == nullptr) ? root : failNode->children[c];
child->output.insert(child->output.end(), child->fail->output.begin(), child->fail->output.end());
q.push(child);
}
}
}
public:
ACAutomaton(const vector<string>& patterns) {
buildTrie(patterns);
buildFailPointers();
}
vector<int> search(const string& text) {
vector<int> matches;
TrieNode* node = root;
for (int i = 0; i < text.size(); ++i) {
char c = text[i];
while (node != nullptr && !node->children.count(c)) {
node = node->fail;
}
if (node == nullptr) {
node = root;
continue;
}
node = node->children[c];
for (int patternIndex : node->output) {
matches.push_back(patternIndex);
}
}
return matches;
}
vector<string> getPatterns() const {
return patterns;
}
};
int main() {
vector<string> patterns = {"he", "she", "his", "hers"};
ACAutomaton ac(patterns);
string text = "ahishers";
vector<int> matches = ac.search(text);
cout << "Matches found at positions: ";
for (int idx : matches) {
cout << patterns[idx] << " ";
}
cout << endl;
return 0;
}
五、AC 自动机的时间复杂度
- 构建 Trie 树：O(m)，其中 m 是所有模式串的总长度。
- 构建失败指针：O(m)，使用 BFS 遍历 Trie 树。
- 匹配过程：O(n + z)，其中 n 是主串长度，z 是匹配成功的次数。
总时间复杂度：O(m + n + z)。
六、AC 自动机的应用场景
- 病毒扫描：检测文本中是否包含已知病毒特征码。
- 关键词过滤：如敏感词检测、广告屏蔽。
- DNA 序列分析：快速查找 DNA 序列中的特定模式。
- 搜索引擎：快速匹配搜索关键词。
七、总结
AC 自动机是一种高效的多模式字符串匹配算法，结合了 Trie 树和 KMP 算法的思想，能够在 O(n + m + z) 的时间复杂度内完成匹配。它的核心是 Trie 树 和 失败指针，适用于需要同时匹配多个模式串的场景。