引入#

kmp算法处理了一个模式串在一个文本串中匹配的场景。如果是多个模式串在一个文本串匹配呢？

Trie树#

由于我们在上一章详细讨论了字典树，这章就不做赘述

Fail指针#

如同kmp算法一样，AC自动机高效的原因也是在失配的时候可以及时调整，避免重复运算，用一个 fail 数组实现这一流程。

fail[i] 所储存的值 u 是存在于字典树中的 i 的最长后缀。

fail[i] 的值可以由比点 i 辈分还高的点的 fail 值得到。我们先来看一下过程

考虑计算 fail[i] 的值：

让 u = fa[i]，也就是i的父节点

如果 fail[u] 的子节点中有 i 的值，那么 fail[i] = fail[u]的那个子节点
如果 fail[u] 的子节点中没有 i 的值，那么 u = fail[u] ，从头继续
如果 u 已经是根节点了，那么停止循环， fail[u] = 0

为什么这样可行呢？

因为 i 的父节点已经帮 i 找好了 i 前一个字符串的最长公共后缀的元素在哪里。对于 i 来说，只要“子承父业”，继承父亲所找到的那个元素就好了，如果“父业”（也就是 fail[fa[i]] 节点）下有他儿子就好。（对应步骤1）

如果没有也没关系。继承不了父亲的也可以沿着父亲找到的那个元素的链条往上爬，再往上找，直到找到某个元素使这个元素的子节点下面有 i 就行。（对应步骤2）如果实在没有直接 fail[i] = 0（对应步骤3）

Fail 指针优化#

看起来很美好，可是如果一直向上追溯肯定时间不够。

我们可以给每个元素都加上“虚拟儿子”，凑齐二十六个字母（如果题目有数字那也要包括）。这样子元素就可以直接“子承父业”， fail[i] = fail[fa[i]].son[i对应的字符的值]（不用上一节一直往上爬（步骤2）了，因为“父业”下面已经有这个儿子了~~（虽然可能是虚拟的）~~）。i的“虚拟儿子” c （也就是 i 原本没有 c 这个儿子）是i.son[c] = fail[i].son[c]。

前面一句话好理解。那么最后一句话呢？

其实“虚拟儿子”就保存着我们上一节循环后的答案。这里“真实儿子”对应着步骤1找到了元素，“虚拟儿子”对应着步骤2没找到元素。因为 i 的虚拟儿子 c 是由 fail[i] 的儿子 c 得到的。如果它是真实的那么最终 i 的虚拟儿子 c 就对应着另一个元素 fail[fa[d]] = i,d的值为c 的 fail[d] 的值，fail[d] = i.son[c]。即使它是虚拟的但他也是由fail[fail[i]] 的儿子 c 得到的。一直向上，和上一节的循环一样。如果遇到了真实的停，直到根节点。只不过是把这个过程从上往下进行了而已。

用BFS（广度优先搜索）从上往下更新，可以保证更新一个节点时比它辈分还大的节点已经更新完了。

引用一句名言

Talk is cheap. Show me the code.

--- Linus

1
queue<int> que;
2
void bfs(){
3
    for(int i=0;i<=25;i++){
4
        if(tr[0][i])que.push(tr[0][i]);
5
    }
6
    while(!que.empty()){
7
        int u=que.front();
8
        que.pop();
9
        for(int i=0;i<=25;i++){
10
            if(!tr[u][i])   tr[u][i]=tr[fail[u]][i];//创建虚拟儿子
11
            else{//更新fail指针
12
                que.push(tr[u][i]);
13
                fail[tr[u][i]]=tr[fail[u]][i];
14
            }
15
        }
16
    }
17
}

查询#

运用虚拟儿子解决了匹配失败的问题。那么匹配成功走真的儿子，匹配失败走假的儿子，就可以忽略这一差别，直接向下走。我们上一章讲了在字符串末尾打上标记，查询的时候就可以直接向下走，然后记录遇到了几个标记，并且把他清零（如果只需要匹配一次的话）。

1
void find(string s){
2
    int u=0,c;
3
    for(int i=0;i<s.length();i++){
4
        c=s[i]-'a';
5
        u=tr[u][c];//向下走一步
6
        ans+=bo[u];
7
        bo[u]=0;//确保同一字符串只被统计一次
8
    }
9
    return;
10
}

代码实践#

洛谷：P3808

1
#include<iostream>
2
#include<string>
3
#include<queue>
4

5
using namespace std;
6

7
#define N 1000009
8

9
int n;
10
int ans,cnt;
11
int fail[N];
12
int tr[N][30];
13
int bo[N];
14

15
void make(string s){
16
    int u=0;
17
    for(int i=0;i<s.length();++i){
18
        int c=s[i]-'a';
19
        if(!tr[u][c]){
20
            tr[u][c]=++cnt;
21
        }
22
        u=tr[u][c];
23
    }
24
    bo[u]++;
25
    return;
26
}
27

28
queue<int> que;
29
void bfs(){
30
    for(int i=0;i<=25;i++){
31
        if(tr[0][i])que.push(tr[0][i]);
32
    }
33
    while(!que.empty()){
34
        int u=que.front();
35
        que.pop();
36
        for(int i=0;i<=25;i++){
37
            if(!tr[u][i])   tr[u][i]=tr[fail[u]][i];//创建虚拟儿子
38
            else{//更新fail指针
39
                que.push(tr[u][i]);
40
                fail[tr[u][i]]=tr[fail[u]][i];
41
            }
42
        }
43
    }
44
}
45

46
void find(string s){
47
    int u=0,c;
48
    for(int i=0;i<s.length();i++){
49
        c=s[i]-'a';
50
        u=tr[u][c];
51
        ans+=bo[u];
52
        bo[u]=0;//确保同一字符串只被统计一次
53
    }
54
    return;
55
}
56

57
int main(){
58
    int n;
59
    string s;
60
    ans=0;cnt=0;
61

62
    cin>>n;
63

64
    //输入模式串
65
    while(n--){
66
        cin>>s;
67
        //建立trie树
68
        make(s);
69
    }
70

71
    //建立next指针
72
    bfs();
73

74
    //输入文本串
75
    cin>>s;
76
    //ac自动机
77
    find(s);
78

79
    cout<<ans<<endl;
80
    return 0;
81
}