欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

浅谈AC自动机

程序员文章站 2022-06-04 12:25:30
...

0.前言

第一眼看,还以为是自动AC机,学了就可以ak虐全场了。
可惜理想很丰满,现实却很骨感,它叫AC自动机,是一种字符串算法
我们都知道KMP算法是可以在一个文本串中找到你想找的一个模式串的位置的,
而AC自动机的主要用处就在于可以把多个模式串匹配到文本串中,并且可以找到一个模式串出现的所有位置,好高级呀。
预备知识:
trie树就够了

一.思想

我们先对所有需要匹配的模式串建立trie树,
然后要建立fail指针,指向与当前后缀相等的前缀,来一张图帮助理解:
浅谈AC自动机
虚线就是我们的fail指针,首先所有开头的字母都指向根。然后,图中h指向另一个子树的h是因为另一个字符串的前缀sh与我当前的后缀sh一样,其他的指针同理。
有了这个东西,当我们匹配不下去的时候,就可以转向fail指针指向的那个节点继续查找,这个时间复杂度就很低。
这就是AC自动机的主要思想。
时间复杂度:O(n)O(n)

二.实现

1.建树

建trie树就不用我说了吧

void insert (char *a){
    int len = strlen (a), now = 0;
    for (int i = 0; i < len; i ++){
        if (! tire[now][a[i] - 'a'])
            tire[now][a[i] - 'a'] = ++ cnt;
        now = tire[now][a[i] - 'a'];
    }
    cntword[now] ++;//记录当前节点有多少个完整的模式串
}

2.预处理fail

这里我们要用bfs,搜索这颗trie树
注意:这个节点的fail要么等于它父亲节点的fail的后一个,要么就是0.

void getfail (){
    queue <int> Q;
    for (int i = 0; i < 26; i ++){//先把所有模式串的开头扔进队列
        if (tire[0][i]){
            fail[tire[0][i]] = 0;//指向根
            Q.push (tire[0][i]);
        }
    }
    while (! Q.empty ()){//bfs
        int f = Q.front ();
        Q.pop ();
        for (int i = 0; i < 26; i ++){
            if (tire[f][i]){
                fail[tire[f][i]] = tire[fail[f]][i];//这个节点的fail等于它父亲节点的fail的后一个
                Q.push (tire[f][i]);
            }
            else
                tire[f][i] = tire[fail[f]][i];
        }
    }
}

3.AC自动机的操作

int ACzdj (char *a){
    int len = strlen (a), now = 0, ans = 0;
    for (int i = 0; i < len; i ++){//遍历文本串每一个字符
        now = tire[now][a[i] - 'a'];
        for (int j = now; j && cntword[j] != -1; j = fail[j]){//找到所有的相同前缀去查找单词数量
            ans += cntword[j];
            cntword[j] = -1;//找到一个节点就附一个-1
        }
    }
    return ans;
}

三.模板

这道模板题:AC自动机
Code:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

#define M 1000005

int n, tire[M][30], cnt, cntword[M], fail[M];

void insert (char *a){
    int len = strlen (a), now = 0;
    for (int i = 0; i < len; i ++){
        if (! tire[now][a[i] - 'a'])
            tire[now][a[i] - 'a'] = ++ cnt;
        now = tire[now][a[i] - 'a'];
    }
    cntword[now] ++;
}
void getfail (){
    queue <int> Q;
    for (int i = 0; i < 26; i ++){
        if (tire[0][i]){
            fail[tire[0][i]] = 0;
            Q.push (tire[0][i]);
        }
    }
    while (! Q.empty ()){
        int f = Q.front ();
        Q.pop ();
        for (int i = 0; i < 26; i ++){
            if (tire[f][i]){
                fail[tire[f][i]] = tire[fail[f]][i];
                Q.push (tire[f][i]);
            }
            else
                tire[f][i] = tire[fail[f]][i];
        }
    }
}
int ACzdj (char *a){
    int len = strlen (a), now = 0, ans = 0;
    for (int i = 0; i < len; i ++){
        now = tire[now][a[i] - 'a'];
        for (int j = now; j && cntword[j] != -1; j = fail[j]){
            ans += cntword[j];
            cntword[j] = -1;
        }
    }
    return ans;
}
int main (){
    char a[M];
    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++){
        scanf ("%s", a);
        insert (a);
    }
    getfail();
    scanf ("%s", a);
    printf ("%d\n", ACzdj (a));
    return 0;
}

谢谢!

相关标签: AC自动机