AcWing 1282. 搜索关键词

题目传送门

一、AC自动机算法流程

1. 构造一棵\(Trie\)，作为\(AC\)自动机的搜索数据结构

2. 构造\(fail\)指针

\(fail\)(失配)数组的定义:从\(a\)串跳到\(b\)串,\(b\)串一定是\(a\)的子串，\(b\)串一定也是\(a\)串某个前缀的后缀

3. 扫描主串进行匹配

二、AC自动机详细图解

1. 首先给定模式串 ash,shex,bcd,sha,然后我们根据模式串建立如下\(Trie\)树:
   

2. 建立失配指针
   \(AC\)自动机就是在\(Trie\)树的基础上，增加一个失配时候用的fail指针，如果当前点匹配失败，则将指针转移到fail指针指向的地方，这样就不用回溯,而可以继续匹配下去了。一般，fail 指针的构建都是用 bfs 实现的。

核心： 当前模式串后缀和fail指针指向的模式串部分前缀相同

例如：题目中给出的总串：yasherhs,模式串为：shel和her,当比较其中的her时，用模式串shel进行比较，当我们找到e并发现下一个要找的不是l，因为模式串shel遍历到字母e的时候的后缀是he可以与另外一个模式串her的部分前缀he匹配,所以可以跳到her的e处,接着再进行匹配，发现模式串her就能与主串的her匹配上，所以保证当前模式串后缀和fail指针指向的模式串部分前缀相同，就能省去很多比较步骤)

(1)先每个模式串的首字母肯定是指向根节点的：

(2)现在第一层 \(bfs\) 遍历完了，开始第二层（根节点为第0层）第二层节点 s 是第一层节点 a的子节点，但是我们还是要从 a - z 遍历，

当我们遍历到 s 的时候，如果存在 s 这个节点，我们就让它的fail指针指向他父亲节点fail 指针指向的那个节点的具有相同字母的子节点;如果不存在这个子节点，它的树节点值也等于父节点的fail指向的节点中具有相同字母的子节点。

三、匹配过程

匹配就很简单了，这里以 ashw 为例：
我们先用 ash 匹配，到 h了发现，ash是一个完整的模式串，则ans++，然后找下一个 w，可是 ash 后面没字母了呀，我们就跳到 h 的 fail 指针指向的那个 h 继续找，还是没有 ? 再跳，结果当前的 h 指向的是根节点，又从根节点找,然而还是没有找到 w，匹配结束（假设如果有w的话，那么模式串shw就可以匹配上ashw）。流程图如下：

四、完整代码

#include 

using namespace std;

const int N = 10010 * 55;    //模式串最长长度,短串
const int M = 1e6 + 10; //长度为m的文章，长串

int n;
//tr:trie树，每个结点最多26个儿子
//cnt:trie的每个结点存在的以此结点结尾的字符串个数
//idx:游标变量，结点号
int tr[N][26], cnt[N], idx;
string str;//字符串变量，前面用做输入模式串，最后一个是文章串
//AC自动机自己的数据结构 q:bfs用的队列 fail:失配指针
int q[N], fail[N];
bool st[N];         //是不是访问过
//构建Trie树
void insert() {
    int p = 0;                              //游标变量
    for (int i = 0; i < str.size(); i++) {  //遍历模式字符串
        int t = str[i] - 'a';               //计算对应的索引号
        if (!tr[p][t]) tr[p][t] = ++idx;    //如果不存在这个结点，则创建之
        p = tr[p][t];                     //走进去
    }
    cnt[p]++;                               //打上字符串完结标识
}

//构建AC自动机(填充失配指针)
void build() {
    int hh = 0, tt = -1;//清空队列，所以前面不需要每次都memset清空q
    for (int i = 0; i < 26; i++)    //查找root的所有26个可能存在的儿子
        if (tr[0][i])             //如果该儿子存在
            q[++tt] = tr[0][i];   //把这个儿子放入队列中

    while (hh <= tt) {          //bfs框架
        int p = q[hh++];        //取出队列头,父结点
        for (int i = 0; i < 26; i++) {  //尝试找出该结点的所有儿子
            int c = tr[p][i];   //子结点
            //如果不存在,这个的失配指针指向,父节点的失配指针对应的相同字节点下
            if (!c) tr[p][i] = tr[fail[p]][i];
            else {
                //存在依旧指向父节点的失配指针下的同子节点
                fail[c] = tr[fail[p]][i];
                q[++tt] = c;//放入队列
            }
        }
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        //多组数据，每次清空
        memset(st, 0, sizeof st);
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(fail, 0, sizeof fail);
        idx = 0;

        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> str;
            //构建Trie树
            insert();
        }
        //构建AC自动机
        build();
        //读入文章长串
        cin >> str;
        int res = 0;
        //j记录当前树节点的指针，初始是根节点
        for (int i = 0, j = 0; i < str.size(); i++) {  //枚举总串str的每一个字母
            int u = str[i] - 'a';
            j = tr[j][u];       //跳到下一个树节点
            int p = j;          //每次从当前树节点开始

            while (!st[p] && p) {
                res += cnt[p];  //累加命中的模式串个数
                cnt[p] = 0;     //去除标记
                st[p] = true;   //设置已统计过
                p = fail[p];    //继续查询
            }
        }
        printf("%d\n", res);
    }
    return 0;
}