C语言实现AC自动机算法

简介

AC自动机（Aho-Corasick自动机）是一种多模式串匹配算法，由Alfred V. Aho和Margaret J. Corasick在1975年提出。它在文本处理、信息检索、生物信息学等领域有着广泛的应用。AC自动机通过构建一个高效的有限状态自动机，能够在一次扫描中同时匹配多个模式串，大大提高了匹配效率。

基础概念

前缀树（Trie树）

前缀树是AC自动机的基础数据结构，它是一种树形结构，用于高效存储和检索字符串集合。Trie树的每个节点代表一个字符，从根节点到叶节点的路径表示一个字符串。插入和查找操作的时间复杂度均为O(m)，其中m是字符串的长度。

失败指针（Fail指针）

失败指针是AC自动机的核心概念。对于Trie树中的每个节点，失败指针指向该节点在Trie树中失配时应该跳转的节点。通过设置失败指针，AC自动机可以在匹配失败时快速跳转到其他可能匹配的位置，从而避免重复扫描。

使用方法

构建Trie树

构建Trie树的过程就是将所有模式串插入到Trie树中。具体步骤如下：

从根节点开始，依次扫描模式串的每个字符。
如果当前字符对应的子节点存在，则移动到该子节点。
如果当前字符对应的子节点不存在，则创建一个新的子节点。
重复步骤2和3，直到模式串的所有字符都被处理完毕。

构建失败指针

构建失败指针的过程可以使用广度优先搜索（BFS）来实现。具体步骤如下：

将根节点的失败指针指向自身。
将根节点的所有子节点的失败指针指向根节点。
使用队列存储待处理的节点，依次处理队列中的节点。
对于当前处理的节点，获取其失败指针指向的节点。
如果当前节点的字符在失败指针指向的节点的子节点中存在，则将当前节点的失败指针指向该子节点。
否则，递归地查找失败指针指向的节点的失败指针，直到找到一个节点，其对应的子节点存在当前字符，或者到达根节点。
将当前节点的失败指针指向找到的节点。
将当前节点的所有子节点加入队列。

模式串匹配

模式串匹配的过程就是在文本中扫描每个字符，利用AC自动机进行匹配。具体步骤如下：

从根节点开始，依次扫描文本的每个字符。
如果当前字符对应的子节点存在，则移动到该子节点。
如果当前字符对应的子节点不存在，则根据失败指针跳转。
重复步骤2和3，直到文本的所有字符都被处理完毕。
在匹配过程中，如果到达一个叶节点，则表示找到了一个模式串。

常见实践

字符串查找

在大量文本中查找多个关键词时，AC自动机可以显著提高查找效率。例如，在搜索引擎中，AC自动机可以用于快速匹配用户输入的关键词。

敏感词过滤

在聊天软件、论坛等应用中，需要对用户输入的内容进行敏感词过滤。AC自动机可以快速识别文本中的敏感词，并进行相应的处理。

最佳实践

内存管理优化

在构建AC自动机时，Trie树可能会占用大量内存。可以使用动态内存分配，并在不需要时及时释放内存。另外，可以考虑使用共享节点的方式，减少内存占用。

性能调优

为了提高AC自动机的性能，可以对Trie树进行压缩，减少节点数量。同时，可以使用位运算等技巧优化字符匹配的过程。

代码示例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CHAR 26

// Trie树节点结构
typedef struct TrieNode {
    struct TrieNode *children[MAX_CHAR];
    struct TrieNode *fail;
    int isEndOfWord;
} TrieNode;

// 创建新的Trie树节点
TrieNode* createNode() {
    TrieNode *newNode = (TrieNode*)malloc(sizeof(TrieNode));
    newNode->isEndOfWord = 0;
    newNode->fail = NULL;
    for (int i = 0; i < MAX_CHAR; i++) {
        newNode->children[i] = NULL;
    }
    return newNode;
}

// 插入模式串到Trie树
void insert(TrieNode *root, const char *word) {
    TrieNode *node = root;
    for (int i = 0; word[i]!= '\0'; i++) {
        int index = word[i] - 'a';
        if (node->children[index] == NULL) {
            node->children[index] = createNode();
        }
        node = node->children[index];
    }
    node->isEndOfWord = 1;
}

// 构建失败指针
void buildFailurePointer(TrieNode *root) {
    TrieNode *queue[1000];
    int front = 0, rear = 0;
    root->fail = root;
    for (int i = 0; i < MAX_CHAR; i++) {
        if (root->children[i]!= NULL) {
            root->children[i]->fail = root;
            queue[rear++] = root->children[i];
        }
    }
    while (front < rear) {
        TrieNode *node = queue[front++];
        for (int i = 0; i < MAX_CHAR; i++) {
            if (node->children[i]!= NULL) {
                TrieNode *failNode = node->fail;
                while (failNode!= root && failNode->children[i] == NULL) {
                    failNode = failNode->fail;
                }
                if (failNode->children[i]!= NULL) {
                    failNode = failNode->children[i];
                }
                node->children[i]->fail = failNode;
                queue[rear++] = node->children[i];
            }
        }
    }
}

// 模式串匹配
void search(TrieNode *root, const char *text) {
    TrieNode *node = root;
    for (int i = 0; text[i]!= '\0'; i++) {
        int index = text[i] - 'a';
        while (node!= root && node->children[index] == NULL) {
            node = node->fail;
        }
        if (node->children[index]!= NULL) {
            node = node->children[index];
        }
        if (node->isEndOfWord) {
            printf("找到模式串: %s\n", text + i - strlen(node->word) + 1);
        }
    }
}

// 释放Trie树内存
void freeTrie(TrieNode *root) {
    for (int i = 0; i < MAX_CHAR; i++) {
        if (root->children[i]!= NULL) {
            freeTrie(root->children[i]);
        }
    }
    free(root);
}

int main() {
    TrieNode *root = createNode();
    insert(root, "he");
    insert(root, "she");
    insert(root, "his");
    insert(root, "hers");

    buildFailurePointer(root);

    const char *text = "ushers";
    search(root, text);

    freeTrie(root);
    return 0;
}

小结

AC自动机是一种强大的多模式串匹配算法，通过构建Trie树和失败指针，能够高效地在文本中匹配多个模式串。在实际应用中，需要根据具体需求对AC自动机进行优化，以提高性能和减少内存占用。

参考资料

Aho, Alfred V.; Corasick, Margaret J. (1975). “Efficient string matching: an aid to bibliographic search”. Communications of the ACM. 18 (6): 333–340.
《算法导论》（第3版），Thomas H. Cormen等著。
《数据结构与算法分析：C语言描述》（第2版），Mark Allen Weiss著。