Aho-Corasick自动机

构建一颗Trie树，然后在每一个节点上标记 代表 当前节点所代表的字符串的 最长的 在Trie树中存在的 后缀 的节点（如果没有则指向根节点，代表空的子串），称为失配指针（fail指针）。

对于在Trie树中存在的子节点，我们要按照父节点的fail指针，将子节点附加到父节点组成的子串之后以推导出子节点的fail指针，所以我们在默认fail指针处的节点已经处理完成的前提之下，将子节点的fail指针 指向 父节点的fail指针 指向的 节点的 对应子节点。

对于在Trie树中不存在的子节点，我们要按照失配指针找到下一个该字母可能有贡献的位置，所以我们直接将它指向父亲的fail指针指向的节点的对应的那个子节点。

为了使处理一个节点时其fail对应的节点已经处理完成，我们采用BFS的方式来处理节点。

void build() {
    queue<node*> Q;
    root->fail = nullptr;

    for (int i = 0; i < 26; i++) {
        if (root->next[i] != nullptr) {
            root->next[i]->fail = root;
            Q.push(root->next[i]);
        }
        else
            root->next[i] = root;
    }

    while (!Q.empty()) {
        node* p = Q.front();
        Q.pop();
        for (int i = 0; i < 26; i++) {
            if (p->next[i] != nullptr) {
                p->next[i]->fail = p->fail->next[i];
                Q.push(p->next[i]);
            }
            else
                p->next[i] = p->fail->next[i];
        }
    }
}

在输入文本串时，可以直接按照文本串中的字符逐个进行指针转移，而不必担心空指针的问题。如果在转移时遇到了在Trie树中标记为单词的节点，则可以断言在文本串的对应位置出现了这个单词。

注意到如果一个短单词是长单词的子串，则在查找时可能查找到长单词而忽略了短单词。所以，对于每一个节点，我们要顺着fail指针不断向上跳并查找单词，直至跳到根节点为止。

void run(const string& str) {
    node* p = root;
    for (const char& c : str) {
        p = p->next[c - 'a'];
        for (node* cur = p; cur != nullptr; cur = cur->fail)
            if (p->isword) {
                // 找到了单词
            }
    }
}

时间复杂度：预处理上限\(O(nl)\)，查询上限\(O(nm)\)，平常一般不会碰到上限

题目：P3808 【模板】AC自动机（简单版）

/*
DOCUMENT NAME "20180810-luogu3808.cpp"
CREATION DATE 2018-08-10
SIGNATURE CODE_20180810_LUOGU3808
COMMENT 【模板】AC自动机（简单版）
*/

#include <cstdlib>
#include <iostream>
#include <queue>
#include <string>
using namespace std;

constexpr int MaxN = 1000000 + 10, MaxTL = 1000000 + 10;

struct node {
    int isword;
    node* next[26];
    node* fail;
};

node* root;
node mem[MaxTL], *memtop = mem;
#define ALLOCATE (++memtop)

void insert(const string& str) {
    if (root == nullptr)
        root = ALLOCATE;
    node* p = root;
    for (char c : str) {
        int v = c - 'a';
        if (p->next[v] == nullptr)
            p->next[v] = ALLOCATE;
        p = p->next[v];
    }
    p->isword++;
}

void build() {
    queue<node*> Q;
    root->fail = nullptr;

    for (int i = 0; i < 26; i++) {
        if (root->next[i] != nullptr) {
            root->next[i]->fail = root;
            Q.push(root->next[i]);
        }
        else
            root->next[i] = root;
    }

    while (!Q.empty()) {
        node* p = Q.front();
        Q.pop();
        for (int i = 0; i < 26; i++) {
            if (p->next[i] != nullptr) {
                p->next[i]->fail = p->fail->next[i];
                Q.push(p->next[i]);
            }
            else
                p->next[i] = p->fail->next[i];
        }
    }
}

int run(const string& str) {
    int ans = 0;
    node* p = root;
    for (const char& c : str) {
        p = p->next[c - 'a'];
        for (node* cur = p; cur != nullptr&&p->isword != -1; cur = cur->fail) {
            ans += p->isword;
            p->isword = -1;
        }
    }
    return ans;
}

int main(int argc, char* argv[]) {
    int n;
    string s;

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

    build();

    cin >> s;
    cout << run(s) << endl;

    return 0;
}