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

AC 自动机的三大组成部分

1. Trie 树（字典树）：存储所有模式串（关键词）。
2. 失败指针（fail 指针）：当当前字符匹配失败时，跳转到另一个状态继续匹配，类似于 KMP 中的 next 数组。
3. 输出函数：标记哪些节点是某个模式串的结尾，并记录匹配到的关键词。

C语言实现步骤详解

第1步：定义 Trie 节点结构

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_CHILD 26  // 假设只处理小写字母 a-ztypedef struct Node {    int count;                    // 记录以该节点结尾的模式串数量    struct Node* fail;            // 失败指针    struct Node* child[MAX_CHILD]; // 子节点数组    char pattern[100];            // 可选：存储匹配到的模式串（用于输出）} Node;// 创建新节点Node* createNode() {    Node* node = (Node*)malloc(sizeof(Node));    node->count = 0;    node->fail = NULL;    memset(node->child, 0, sizeof(node->child));    strcpy(node->pattern, "");    return node;}

第2步：插入模式串到 Trie 树

void insertPattern(Node* root, const char* pattern) {    Node* current = root;    for (int i = 0; pattern[i] != '\0'; i++) {        int index = pattern[i] - 'a';        if (current->child[index] == NULL) {            current->child[index] = createNode();        }        current = current->child[index];    }    current->count++;  // 标记为一个模式串的结尾    strcpy(current->pattern, pattern); // 保存模式串}

第3步：构建失败指针（BFS 遍历）

这是 AC 自动机最核心的部分！我们使用队列进行广度优先搜索（BFS）来设置每个节点的 fail 指针。

#include <queue>  // 注意：纯 C 语言需自己实现队列，此处为简化用伪代码思路// 实际 C 语言中可用数组模拟队列void buildFailPointer(Node* root) {    // 使用数组模拟队列（最大节点数假设为1000）    Node* queue[1000];    int front = 0, rear = 0;    // 初始化：root 的 fail 指向自己（或 NULL），子节点 fail 指向 root    root->fail = root;    for (int i = 0; i < MAX_CHILD; i++) {        if (root->child[i] != NULL) {            root->child[i]->fail = root;  // 第一层子节点失败指针指向根            queue[rear++] = root->child[i];        } else {            root->child[i] = root;  // 优化：空子节点直接指向根（避免后续判断）        }    }    // BFS 构建 fail 指针    while (front < rear) {        Node* current = queue[front++];        for (int i = 0; i < MAX_CHILD; i++) {            if (current->child[i] != NULL) {                Node* child = current->child[i];                // 找到父节点的 fail 节点的对应子节点                child->fail = current->fail->child[i];                queue[rear++] = child;            }        }    }}

第4步：匹配文本并输出结果

void searchText(Node* root, const char* text) {    Node* current = root;    printf("匹配结果：\n");    for (int i = 0; text[i] != '\0'; i++) {        int index = text[i] - 'a';        // 沿着 fail 指针跳转，直到找到匹配或回到根        while (current != root && current->child[index] == NULL) {            current = current->fail;        }        current = current->child[index];        // 检查当前节点及其 fail 链上是否有输出        Node* temp = current;        while (temp != root && temp->count > 0) {            printf("在位置 %d 找到关键词: %s\n", i + 1, temp->pattern);            temp->count = 0; // 避免重复输出（可选）            temp = temp->fail;        }    }}

第5步：主函数测试

int main() {    Node* root = createNode();    // 插入多个模式串    insertPattern(root, "he");    insertPattern(root, "she");    insertPattern(root, "his");    insertPattern(root, "hers");    // 构建失败指针    buildFailPointer(root);    // 测试文本    char text[] = "ushers";    searchText(root, text);    return 0;}

总结

通过本教程，你已经掌握了如何用 C语言 实现 AC自动机 这一强大的多模式匹配算法。虽然代码看起来有点复杂，但只要理解了 Trie 树和失败指针的构建逻辑，就能灵活应用。

记住，AC 自动机的时间复杂度为 O(n + m + z)，其中 n 是文本长度，m 是所有模式串总长度，z 是匹配结果数量——这比逐个匹配快得多！

现在，你可以尝试扩展这个程序：支持大小写字母、中文（需 UTF-8 处理）、或用于实际项目如敏感词过滤系统。加油，你已经迈出了高性能字符串处理的第一步！

SEO关键词回顾：AC自动机、C语言字符串匹配、多模式匹配算法、AC自动机实现