AcWing 1282. 搜索关键词

\(AcWing\) \(1282\). 搜索关键词

一、题目描述

给定 \(n\) 个长度不超过 \(50\) 的由小写英文字母组成的单词，以及一篇长为 \(m\) 的文章。

请问，其中有多少个单词在文章中出现了。

注意：每个单词不论在文章中出现多少次，仅累计 \(1\) 次。

输入格式
第一行包含整数 \(T\)，表示共有 \(T\) 组测试数据。

对于每组数据，第一行一个整数 \(n\)，接下去 \(n\) 行表示 \(n\) 个单词，最后一行输入一个字符串，表示文章。

输出格式
对于每组数据，输出一个占一行的整数，表示有多少个单词在文章中出现。

数据范围
\(1≤n≤10^4,1≤m≤10^6\)

输入样例：

1
5
she
he
say
shr
her
yasherhs

输出样例：

3

二、\(AC\)自动机详细图解

视频讲解
这个视频讲解的很棒，对于学习\(AC\)自动机是个捷径~

步骤

• 根据模式串建立\(Trie\)树
• 构建失配指针
• 在构建的\(AC\)自动机上跑文本串

\(AC\)自动机就是在\(Trie\)树的基础上，增加一个失配时用的ne指针，如果当前点匹配失败，则将指针转移到ne指针指向的地方，这样就可以不用重头再来,尽可能的利用已经知道的信息，能少退就少退。一般，ne 指针的构建是用 bfs 实现的。

举个栗子：

我们需要只遍历一遍文本串(母串或长串)就找出所有单词表中存在的单词（只遍历一遍的想法和\(KMP\)算法有异曲同工之妙）。

　　我们先根据字符集合{she,he,say,shr,her}建立字典树如上图所示，然后我们拿着yasherhs去匹配，发现前两个字符无法匹配，跳过，第三个字符开始，she可以匹配，记录下来，继续往后走发现没有匹配了，结果就是该文本串只存在一个单词，很明显，答案是错的，因为存在she、he、her三个单词！

　　可以发现的是使用文本串在字典树上进行匹配的时候，找到了一个单词结点后还应该看看有没有以该单词结点的后缀为 前缀的其他单词，比如she的后缀he是单词he和her的前缀。因此就需要一个失配指针在发现失配的时候指向其他存在e的结点，来 安排之后应该怎么办。

　　总的来说，AC自动机中失配指针和\(KMP\)中ne数组的作用是一致的，就是要想在只遍历一遍文本串的前提下，找到全部匹配模板，就必须提前安排好匹配过程中失配后怎么办。具体如何安排就是怎么在字典树上加失配边的问题了（即如何构造一个\(AC\)自动机）。

如何创建失配指针？

规则如下：

• 根结点的ne指针为空（或者它自己）；

• 直接和根结点相连的结点，如果这些结点失配，就只能重新开始匹配，故它们的ne指针指向根结点；

• 其他结点，设当前结点为father,其孩子结点为child。要寻找child的ne指针，需要看father的ne指针指向的结点，假设是tmp,要看tmp的孩子中有没有和child所代表的字符相同的，有则child的ne指针指向tmp的这个孩子结点，没有则继续沿着tmp的ne指针往上走，如果找到相同，就指向，如果一直找到了根结点的ne也就是空的时候，child的ne指针就指向root，表示重新从根结点开始匹配。

爹，我整不下去了，你有没有双胞胎兄弟（叔叔伯伯都行），要是有的话，我找他们看看有没有哪个孩子长的和我一样漂亮，有的话，就转给他们继续处理~

其中考察father的ne指针指向的结点有没有和child相同的结点，包括继续往上，就保证了前缀是相同的，比如刚才寻找右侧h的孩子结点e的ne指针时，找到右侧h的ne指针指向左侧的h结点，他的孩子中有e，就将右侧h的孩子e的ne指针指向它就保证了前缀h是相同的。

　　这样，就用ne指针来安排好每次失配后应该跳到哪里，而ne指针跳到哪里，说明从根结点到这个结点之前的字符串已经匹配过了，从而避免了重复匹配，也就完美的解决了只遍历一次文本串就找出所有单词的问题。

三、朴素版本【了解，不用背】

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

const int N = 55 * 1e4 + 10; // n个单词
const int M = 1e6 + 10;      //长度为m的文章

int n;
int tr[N][26], cnt[N], idx;         // Trie树，每个结点的结束标识数组cnt,结点号计数器idx,二维代表最多可能有26条不同走向的边
char s[M];                          // 字符串数组
int q[N], ne[N];                    // AC自动机构建需要的队列和失配指针

// Trie树构建
void insert(char *s) {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int t = s[i] - 'a';
        if (!tr[p][t]) tr[p][t] = ++idx;
        p = tr[p][t];
    }
    cnt[p]++;
}

//构建AC自动机
void build() {
    int hh = 0, tt = -1;
    // 树根和树根下一层的失配边都连到树根上，所以从树根下一层开始bfs
    for (int i = 0; i < 26; i++)
        if (tr[0][i]) q[++tt] = tr[0][i];

    while (hh <= tt) {
        int t = q[hh++];
        for (int i = 0; i < 26; i++) {        // t节点有哪些出边
            int p = tr[t][i];                 // p是 t通过i这条边到达的子节点
            if (!p) continue;                 // 如果p并不存在

            int j = ne[t];                    // t的失配指针指向了j
            while (j && !tr[j][i]) j = ne[j]; // p需要它父亲t的失配指针j=ne[t]出发，一直跳到有i这条边为止,当然，也可能跳到了根也找不到i这条边
            if (tr[j][i]) j = tr[j][i];       // 如果最终的停止节点j，有i这条边，则进入tr[j][i]这个点，这个点就是节点p失配后的指向节点。当然，ne[p]也可能跳回了根
            ne[p] = j;                        //填充儿子节点p的失配指针为它父亲给找的最佳匹配j

            q[++tt] = p; //将节点p放入队列
        }
    }
}

int query(char *s) {
    int res = 0;
    int j = 0; //从root=0开始对AC自动机进行查找
    for (int i = 0; s[i]; i++) {
        int t = s[i] - 'a';
        while (j && !tr[j][t]) j = ne[j]; // 一直跳到有t这条边的节点处或者跳到root停止
        if (tr[j][t]) j = tr[j][t];       // 如果存在，则向下走一步，否则j回到树根

        // 累加计数
        int p = j;
        while (p && ~cnt[p]) {
            res += cnt[p];
            cnt[p] = -1;
            p = ne[p];
        }
    }
    return res;
}

int main() {
    //加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;

    while (T--) {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
        idx = 0;

        // Trie树
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> s;
            insert(s);
        }

        // ac自动机
        build();

        // 查询
        cin >> s;
        printf("%d\n", query(s));
    }
    return 0;
}

　
其实，这是一个不断回溯的过程，在代码实现时，我们一般采用的是\(while\)循环或者递归来不断的向上进行查找，但这样效率上会差一些。有没有更好的办法呢？这得益于我们采用的\(bfs\)策略，我们通过自顶向下的覆盖方式，将上面的信息继承到下面去，换句话说，就是不用儿子去找父亲问，父亲再找爷爷问，这太麻烦了，而且爷爷将答案准备好，告诉父亲，父亲将答案保存好，儿子可以直接获取到。这时就不再是一个\(Trie\)树了，而是一个\(Trie\)图了,有点类似于并查集的路径压缩~

四、\(Trie\)图优化版本【背诵记忆】

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

const int N = 55 * 1e4 + 10;
const int M = 1e6 + 10;

int n;
int tr[N][26], cnt[N], idx;
char s[M];
int q[N], ne[N];

void insert(char *s) {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int t = s[i] - 'a';
        if (!tr[p][t]) tr[p][t] = ++idx;
        p = tr[p][t];
    }
    cnt[p]++;
}

void bfs() {
    int hh = 0, tt = -1;
    for (int i = 0; i < 26; i++)
        if (tr[0][i]) q[++tt] = tr[0][i];

    while (hh <= tt) {
        int t = q[hh++];
        for (int i = 0; i < 26; i++) {
            int p = tr[t][i];
            // 如果p不空，t读i不会失配，则p的ne指针应该连到其父亲的ne指针的i边，和未优化的上面一样
            if (p) ne[p] = tr[ne[t]][i], q[++tt] = p;
            // 如果p空，则处于t读i边会失配，那么直接将最终跳的点连到下面即可
            else
                tr[t][i] = tr[ne[t]][i];
        }
    }
}

int query(char *s) {
    int p = 0;
    int res = 0;
    for (int i = 0; s[i]; i++) {
        p = tr[p][s[i] - 'a'];
        for (int j = p; j; j = ne[j]) {
            if (cnt[j] == -1) break;
            res += cnt[j];
            cnt[j] = -1;
        }
    }
    return res;
}

int main() {
    //加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
        idx = 0;

        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> s;
            insert(s);
        }

        bfs();
        cin >> s;
        printf("%d\n", query(s));
    }
    return 0;
}