Trie 图 AC自动机

Trie 图就是在 Trie 树的基础上增加了后缀节点的概念以及用法，

可以解决如以下的问题：给一个很长很长的母串 长度为n，然后给m个小的模式串。求这m个模式串里边有多少个是母串的字串。

// Trie图 
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

typedef struct Trie{
    bool flag;
    struct Trie *behind, *next[26];
}Trie;

int main(){
    int T;
    string str;
    // 初始化根节点 
    Trie *root = new Trie;
    root->behind = NULL;
    root->flag = false;
    for(int i = 0; i< 26; i++)
        root->next[i] = NULL;
    // 建字典树    
    cin >> T;
    while(T--){
        Trie *p = root;
        cin >> str;
        for(int i = 0; str[i]; i++){
            int j = str[i] - 'a';
            if(!p->next[j]){
                Trie *q = new Trie;
                q->behind = NULL;
                q->flag = false;
                for(int k = 0; k< 26; k++) q->next[k] = NULL;
                
                p->next[j] = q;
            }
            p = p->next[j];
        }
        p->flag = true;
    }
    // 求后缀节点 
    queue<Trie*>Q;
    root->behind = root;
    for(int i = 0; i< 26; i++){
        if(!root->next[i]){
            root->next[i] = root;
        }
        else{
            root->next[i]->behind = root;
            Q.push(root->next[i]);
        }
    }
    
    while(!Q.empty()){
        Trie *p = Q.front(), *q = p->behind;
        Q.pop();
        for(int i = 0; i< 26; i++){
            if(!p->next[i]){
                p->next[i] = q->next[i];
            }
            else{
                p->next[i]->behind = q->next[i];
                Q.push(p->next[i]);
            }
        }
    }
    // 查找 
    string s;
    cin >> s;
    Trie *p = root;
    bool tag = false;
    for(int i = 0; s[i]; i++){
        int j = s[i] - 'a';
        p = p->next[j];
        if(p->flag){
            tag = true;
            cout << "YES" << endl;
            break;
        }
    }
    if(!tag)
        cout << "NO" << endl;
    
    return 0;
}