洛谷 P3808 【模板】AC自动机（简单版）

Description:

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

Input:

第一行一个n，表示模式串个数；

下面n行每行一个模式串；

下面一行一个文本串。

Output

一个数表示答案

Sample Input:

2
a
aa
aa

Sample Output:

2

题目链接

顾“题”思义，题目是一个AC自动机的模板裸题。

AC自动机就是将多个模式串建立字典树(Trie Tree)，在树上进行类KMP操作，以此与主串进行匹配。

AC自动机详解:

AC自动机

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 5;

// AC自动机
struct AhoCorasickAutomaton {
    // 子节点记录数组
    int Son[maxn][26];
    int Val[maxn];
    // 失配指针Fail数组
    int Fail[maxn];
    // 节点数量
    int Tot;

    // Trie Tree初始化
    void TrieInit() {
        Tot = 0;
        memset(Son, 0, sizeof(Son));
        memset(Val, 0, sizeof(Val));
        memset(Fail, 0, sizeof(Fail));
    }

    // 计算字母下标
    int Pos(char X) {
        return X - 'a';
    }

    // 向Trie Tree中插入Str模式字符串
    void Insert(string Str) {
        int Cur = 0, Len = int(Str.length());
        for (int i = 0; i < Len; ++i) {
            int Index = Pos(Str[i]);
            if (!Son[Cur][Index]) {
                Son[Cur][Index] = ++Tot;
            }
            Cur = Son[Cur][Index];
        }
        Val[Cur]++;
    }

    // Bfs求得Trie Tree上失配指针
    void GetFail() {
        queue<int> Que;
        for (int i = 0; i < 26; ++i) {
            if (Son[0][i]) {
                Fail[Son[0][1]] = 0;
                Que.push(Son[0][i]);
            }
        }
        while (!Que.empty()) {
            int Cur = Que.front(); Que.pop();
            for (int i = 0; i < 26; ++i) {
                if (Son[Cur][i]) {
                    Fail[Son[Cur][i]] = Son[Fail[Cur]][i];
                    Que.push(Son[Cur][i]);
                }
                else {
                    Son[Cur][i] = Son[Fail[Cur]][i];
                }
            }
        }
    }

    // 询问Str中出现的模式串数量
    int Query(string Str) {
        int Len = int(Str.length());
        int Cur = 0, Ans = 0;
        for (int i = 0; i < Len; ++i) {
            Cur = Son[Cur][Pos(Str[i])];
            for (int j = Cur; j && ~Val[j]; j = Fail[j]) {
                Ans += Val[j];
                Val[j] = -1;
            }
        }
        return Ans;
    }
};

int main(int argc, char *argv[]) {
    AhoCorasickAutomaton AC;
    AC.TrieInit();
    int N;
    cin >> N;
    string Str;
    for (int i = 0; i < N; ++i) {
        cin >> Str;
        AC.Insert(Str);
    }
    AC.GetFail();
    cin >> Str;
    cout << AC.Query(Str) << endl;
    return 0;
}