AC自动机

要学AC自动机需要自备两个前置技能:KMP和trie树 其中,KMP是用于一对一的字符串匹配,而trie虽然能用于多模式匹配,但是每次匹配失败都需要进行回溯,如果模式串很长的话会很浪费时间,所以AC自动机应运而生,如同Manacher一样,AC自动机利用某些操作阻止了模式串匹配阶段的回溯,将时间复杂度优化到了\(O ( n )\)，n为文本串长度

问题描述

给定n个模式串和11个文本串，求有多少个模式串在文本串里出现过。

注意：是出现过，就是出现多次只算一次。

我们将n个模式串建成一颗Trie树，建树的方式和建Trie完全一样。

预处理：Tire树的构建

image-20240221122341606

构建如下，绿色表示终止，不懂可以看前几篇博客

Fail指针

3个原则：

1.构建fail指针的层次遍历

2.root节点的fail指针指向自己本身

3.如果当前父节点的fail指针指向的节点存在与当前节点一样的子节点，则当前节点的fail种子很指向该节点。

毫无疑问

root指向自己

s和h指向root，因为s的父节点根节点并没有与当前节点一样的节点，因为不会重复，这就是为什么第一层都是指向根节点查的原因。

接下来a节点，他的父节点是s，s指向的fair为根，并没有指向a，因此也指向根节点。

而h得父节点s也指向根节点，根节点有指向h得，因此h就指向h，如图：

image-20240221133740234

同理，e也指向root，y也是root，e父节点是h，h指向上面的h,上面的h指向的是e，因此有了

image-20240221133858030

其实这里已经可以看出Fail的实质含义：

如果一个点i的Fail指针指向j。那么root到j的字符串是root到i的字符串的一个后缀。

首先我们可以确定，每一个点i的Fail指针指向的点的深度一定是比i小的。（Fail指的是后缀）

AC 自动机（简单版）

题目描述

给定 \(n\) 个模式串 \(s_i\) 和一个文本串 \(t\)，求有多少个不同的模式串在文本串里出现过。
两个模式串不同当且仅当他们编号不同。

输入格式

第一行是一个整数，表示模式串的个数 \(n\)。
第 \(2\) 到第 \((n + 1)\) 行，每行一个字符串，第 \((i + 1)\) 行的字符串表示编号为 \(i\) 的模式串 \(s_i\)。
最后一行是一个字符串，表示文本串 \(t\)。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

1
2
3
4
5
3
a
aa
aa
aaa

样例输出 #1

1
3

样例 #2

样例输入 #2

1
2
3
4
5
6
4
a
ab
ac
abc
abcd

样例输出 #2

1
3

样例 #3

样例输入 #3

1
2
3
4
2
a
aa
aa

样例输出 #3

1
2

提示

样例 1 解释

\(s_2\) 与 \(s_3\) 编号（下标）不同，因此各自对答案产生了一次贡献。

样例 2 解释

\(s_1\)，\(s_2\)，\(s_4\) 都在串 abcd 里出现过。

数据规模与约定

  • 对于 \(50\%\) 的数据，保证 \(n = 1\)。
  • 对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^6\)，\(1 \leq |t| \leq 10^6\)，\(1 \leq \sum\limits_{i = 1}^n |s_i| \leq 10^6\)。\(s_i, t\) 中仅包含小写字母。
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =  2*1e6+9;
int trie[maxn][26]; //字典树
int cntword[maxn];  //记录该单词出现次数
int fail[maxn];     //失败时的回溯指针
int cnt ;

void insertWords(string s){
    int p = 0;
    for(int i=0;i<s.size();i++){
        int next = s[i] - 'a';
        if(!trie[p][next])
            trie[p][next] = ++cnt;
        root = trie[p][next];
    }
    cntword[p]++;      //当前节点单词数+1
}
void getFail(){
    queue <int>q;
    for(int i=0;i<26;i++){      //将第二层所有出现了的字母扔进队列
        if(trie[0][i]){
            fail[trie[0][i]] = 0;
            q.push(trie[0][i]);
        }
    }

//fail[now]    ->当前节点now的失败指针指向的地方
//tire[now][i] -> 下一个字母为i+'a'的节点的下标为tire[now][i]
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i=0;i<26;i++){      //查询26个字母
            if(trie[now][i]){
                //如果有这个子节点为字母i+'a',则
//让这个节点的失败指针指向(((他父亲节点)的失败指针所指向的那个节点)的下一个节点)
                //有点绕,为了方便理解特意加了括号
                fail[trie[now][i]] = trie[fail[now]][i];
                q.push(trie[now][i]);
            }
            else//否则就让当前节点的这个子节点
                //指向当前节点fail指针的这个子节点
                trie[now][i] = trie[fail[now]][i];
        }
    }
}


int query(string s){
    int now = 0,ans = 0;
    for(int i=0;i<s.size();i++){    //遍历文本串
        now = trie[now][s[i]-'a'];  //从s[i]点开始寻找
        for(int j=now;j && cntword[j]!=-1;j=fail[j]){
            //一直向下寻找,直到匹配失败(失败指针指向根或者当前节点已找过).
            ans += cntword[j];
            cntword[j] = -1;    //将遍历国后的节点标记,防止重复计算
        }
    }
    return ans;
}

int main() {
    int n;
    string s;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> s ;
        insertWords(s);
    }
    fail[0] = 0;
    getFail();
    cin >> s ;
    cout << query(s) << '\n';
    return 0;
}