还记得2019年暑假，gy在英乐华翻开ybt提高篇的目录

概述

通常来讲，KMP 算法用来处理单模式串匹配问题。而若要处理多模式串的问题，就要引出 AC自动机 。

AC自动机 是以 Trie 的结构为基础，结合 KMP 的思想建立的。

步骤

  1. 将所有模式串构建成一棵 Trie 树

  2. 对 Trie 上所有节点构造失配指针（最长后缀）

  3. 利用失配指针对主串进行匹配。

流程

  • 构建指针

    记 $tr[p][c]=v$ 表示结点 $v$ 的父结点 $p$ 通过字符 $c$ 指向 $v$ 。

    记 $fail[u]$ 表示 $u$ 的失配指针，即 $u$ 的最长后缀。

    1. 若 $tr[u][i]$ 存在，则 $fail[tr[u][i]]$ 可以由 $fail[u]$ 增加一个字符 $i$ 得到
    2. 否则，直接将 $tr[u][i]$ 指向 $tr[fail[u]][i]$ 的状态 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void build(){
        for(int i=0;i<26;i++)
            if(tr[0][i])q.push(tr[0][i]);
        while(q.size()){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                if(tr[u][i]){
                    fail[tr[u][i]]=tr[fail[u]][i];
                    q.push(tr[u][i]);
                }
                else tr[u][i]=tr[fail[u]][i];
            }
        }
    }

  • 匹配函数

    以P3808 【模板】AC自动机（简单版）的要求为例

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int query(char *s) {
        int u=0,res=0;
        for(int i=1;s[i];i++) {
            u=tr[u][t[i]-'a'];
            for(int j=u;j && e[j]!=-1;j=fail[j]){
                res+=e[j],e[j]=-1;
            }
        }
        return res;
    }

板子

P5357 【模板】AC自动机（二次加强版）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;

const int N=2e5+5;
int head[N],to[N],ne[N],tot;
int n,tr[N][26],fail[N],ch,book[N],sz[N];
char s[N*10];
queue<int> q;

void build(){
    for(int i=0;i<26;i++)
        if(tr[0][i])q.push(tr[0][i]);
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            if(tr[u][i]){
                fail[tr[u][i]]=tr[fail[u]][i];
                q.push(tr[u][i]);
            }
            else tr[u][i]=tr[fail[u]][i];
        }
    }
}

inline void add(int u,int v){
    to[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}

void dfs(int u){
    for(int i=head[u];i;i=ne[i]){
        int v=to[i];
        dfs(v);
        sz[u]+=sz[v];
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        int u=0;
        for(int j=1;s[j];j++){
            if(!tr[u][s[j]-'a'])tr[u][s[j]-'a']=++ch;
            u=tr[u][s[j]-'a'];
        }
        book[i]=u;
    }
    build();
    scanf("%s",s+1);
    for(int u=0,i=1;s[i];i++){
        u=tr[u][s[i]-'a'];
        sz[u]++;
    }
    for(int i=1;i<=ch;i++){
        add(fail[i],i);
    }
    dfs(0);
    for(int i=1;i<=n;i++)printf("%d\n",sz[book[i]]);
    return 0;
}