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

AC自动机的核心结构

AC自动机主要由三部分组成：

1. Trie树：用于存储所有模式串。
2. 失败指针（fail）：当当前字符匹配失败时，跳转到最长公共后缀对应的节点。
3. 输出函数：记录以当前节点结尾的模式串。

C语言实现步骤

1. 定义节点结构

struct Node {    int count;                 // 记录以该节点结尾的模式串数量    struct Node* fail;         // 失败指针    struct Node* children[26]; // 假设只处理小写字母};// 创建新节点struct Node* createNode() {    struct Node* node = (struct Node*)malloc(sizeof(struct Node));    node->count = 0;    node->fail = NULL;    for (int i = 0; i < 26; i++) {        node->children[i] = NULL;    }    return node;}  

2. 构建Trie树

void insertPattern(struct Node* root, char* pattern) {    struct Node* current = root;    for (int i = 0; pattern[i] != '\0'; i++) {        int index = pattern[i] - 'a';        if (current->children[index] == NULL) {            current->children[index] = createNode();        }        current = current->children[index];    }    current->count++; // 标记此处有一个模式串结束}  

3. 构建失败指针（BFS）

void buildFailPointer(struct Node* root) {    struct Node* queue[1000];    int front = 0, rear = 0;    // 初始化：根的所有子节点的fail指向root，并入队    for (int i = 0; i < 26; i++) {        if (root->children[i] != NULL) {            root->children[i]->fail = root;            queue[rear++] = root->children[i];        }    }    // BFS构建fail指针    while (front < rear) {        struct Node* current = queue[front++];        for (int i = 0; i < 26; i++) {            if (current->children[i] != NULL) {                struct Node* child = current->children[i];                struct Node* f = current->fail;                // 沿着fail链向上找，直到找到有对应子节点的祖先                while (f != NULL && f->children[i] == NULL) {                    f = f->fail;                }                child->fail = (f == NULL) ? root : f->children[i];                // 累加输出：如果fail节点是模式串结尾，也应被计入                child->count += child->fail->count;                queue[rear++] = child;            }        }    }}  

4. 匹配文本

int searchText(struct Node* root, char* text) {    struct Node* current = root;    int totalMatches = 0;    for (int i = 0; text[i] != '\0'; i++) {        int index = text[i] - 'a';        // 如果当前节点没有对应子节点，沿fail指针回退        while (current != root && current->children[index] == NULL) {            current = current->fail;        }        if (current->children[index] != NULL) {            current = current->children[index];        }        // 累加当前节点及fail链上的所有匹配        totalMatches += current->count;    }    return totalMatches;}  

完整使用示例

#include <stdio.h>#include <stdlib.h>#include <string.h>// 上面定义的结构体和函数...int main() {    struct Node* root = createNode();    // 插入多个模式串    insertPattern(root, "he");    insertPattern(root, "she");    insertPattern(root, "his");    insertPattern(root, "hers");    // 构建失败指针    buildFailPointer(root);    // 在文本中搜索    char text[] = "ahishers";    int matches = searchText(root, text);    printf("Total matches: %d\n", matches); // 输出：3（包含 "his", "she", "hers"）    return 0;}  

总结

通过本文，你已经掌握了用C语言实现AC自动机的基本方法。这种多模式匹配算法在实际工程中非常有用，比如敏感词过滤、病毒特征码扫描等场景。虽然代码看起来有点复杂，但只要理解了Trie树和失败指针的思想，就能轻松掌握。

记住，AC自动机的关键在于：构建Trie → 设置fail指针 → 一次扫描完成所有匹配。希望这篇教程能帮助你从零开始理解和实现这个强大的算法！