【模板】AC自动机-白红宇

【模板】AC自动机

阅读量：162 次

发布时间：2019-02-28

本文共 2516 字，大约阅读时间需要 8 分钟。

AC自动机（简易版）与AC自动机（二次优化版）的实现与原理分析

AC自动机作为一种高效的数据处理结构，在许多领域得到了广泛应用。本文将详细介绍两种AC自动机的实现版本，并分析其核心原理与优化点。

AC自动机（简易版）

AC自动机的核心思想是通过将字符串转换为节点结构，从而实现快速的字符串匹配操作。这种结构在文本处理、搜索引擎关键词检索等场景中表现出色。以下是简易版AC自动机的实现逻辑：

节点结构设计：

每个节点包含以下属性：
- cnt：记录该节点的出现次数
- fail：表示该节点的失败链接（即最大公前缀节点）
- nxt：表示该节点的下一个节点

插入逻辑：

对于一个字符串 s，从根节点开始，逐个字符遍历，构建新的节点，并根据现有节点设置 nxt 和 fail 属性。

查询逻辑：

在查询时，从根节点出发，沿着 nxt 链接，直到找到匹配的节点。

失败时，通过 fail 链接回到最近的公共前缀节点，继续查询。

时间复杂度分析：

查询时间复杂度为 O(2 * len(T))，其中 len(T) 为目标字符串的长度。这是因为在最坏情况下，可能需要遍历两次节点。

AC自动机（二次优化版）

在简易版的基础上，二次优化版增加了对节点排序的逻辑，以进一步提升性能。这种优化主要适用于处理大规模数据时的性能瓶颈问题。

核心改动：

在插入节点时，新增了对节点排序的逻辑，确保新插入的节点尽可能靠近已有的节点，减少查找时的链状结构。

查询逻辑不变：

查询过程保持一致，通过 nxt 和 fail 链接实现快速匹配。

优化效果：

减少了查找过程中的节点跳转次数，从而提升了整体查询效率。

在处理大规模词典时，显著降低了内存占用和访问时间。

代码示例

以下是两种版本的代码示例，供参考：

#include 
   
    
using namespace std;
const int MAXC = 26;
const int N = 1e6 + 5;
struct node {
    int cnt, fail;
    int nxt[MAXC];
};
int root = 0, tot = 1, res = 0, T, n;
queue
    
      Q;
char article[N], word[N];
void insert(char *s) {
    int len = strlen(s), r = 1;
    for (int i = 0; i < len; ++i) {
        int c = s[i] - 'a';
        if (!t[r].nxt[c]) {
            t[r].nxt[c] = ++t[tot++];
            t[tot].cnt = 1;
            t[tot].fail = root;
            tot++;
        }
        r = t[r].nxt[c];
        if (r != root && !t[t[r].fail].nxt[c])
            t[t[r].fail].nxt[c] = t[r];
    }
}
int insert(char *s) {
    int len = strlen(s), r = 1;
    for (int i = 0; i < len; ++i) {
        int c = s[i] - 'a';
        if (!t[r].nxt[c]) {
            t[r].nxt[c] = ++t[tot++];
            t[tot].cnt = 1;
            t[tot].fail = root;
            tot++;
        }
        r = t[r].nxt[c];
        if (r != root && !t[t[r].fail].nxt[c])
            t[t[r].fail].nxt[c] = t[r];
    }
}

#include 
   
    
using namespace std;
const int MAXC = 26;
const int N = 2e6 + 5;
struct node {
    int cnt, end, fail;
    int nxt[MAXC];
};
int root = 0, tot = 1, res = 0, T, n, ans[N];
int c[N], in[N];
queue
    
      Q;
int insert(char *s) {
    int len = strlen(s), r = 1;
    for (int i = 0; i < len; ++i) {
        int c = s[i] - 'a';
        if (!t[r].nxt[c]) {
            t[r].nxt[c] = ++t[tot++];
            t[tot].cnt = 1;
            t[tot].fail = root;
            t[tot].end = 0;
            tot++;
        }
        r = t[r].nxt[c];
        if (r != root && !t[t[r].fail].nxt[c])
            t[t[r].fail].nxt[c] = t[r];
    }
    return r;
}

总结

AC自动机通过将字符串转换为节点结构，实现了快速的前缀匹配操作。其核心优势在于支持高效的多模式匹配，同时具有较低的时间复杂度和空间复杂度。在实际应用中，可以根据具体需求选择适合的版本，以达到最佳性能。

转载地址：http://lown.baihongyu.com/

你可能感兴趣的文章