trie树 & ac自动机

trie树

trie树就是字典树，可以理解为单词树，树上每条边是字母，被标记的节点表示根到这个节字母组成了单词。

数据结构：用二维数组trie[maxn][N],tire[u][c]表示树上编号为u的父节点以边为c单词连接到的儿子的编号。
创建trie树：每次添加一个单词，若当前路径已建立此以连接此单词为边的儿子节点就沿着走，否则建立新的节点。

学习链接：浅谈Trie树

Trie树模板

const int maxn=5e5+7;
const int N=26;
struct Tire{
    int trie[maxn][N],tot;
    bool book[maxn];
    void Init(){
        memset(trie,0,sizeof trie);
        memset(book,0,sizeof book);
        tot=0;
    }
    void Insert(string a){
        int u=0;
        for(int i=0;i<a.size();++i){
            int v=a[i]-'a';
            if(trie[u][v]==0){
               trie[u][v]=++tot;
            }
            u=trie[u][v];
        }
        book[u]=true;
    }
}test;

例题：
Phone List

#include<iostream>
#include<set>
#include<string.h>
#include<string>
#include<stdio.h>
using namespace std;
struct Tire{
    int trie[100100][11],tot;
    bool book[100100];
    bool Insert(string a){
        int u=0;
        bool f=false;
        for(int i=0;i<a.size();++i){
            int v=a[i]-'0';
            if(book[u]==true) f=true;
            if(trie[u][v]==0){
               trie[u][v]=++tot;
            }
            u=trie[u][v];
        }

        if(book[u]==true) f=true;
        book[u]=true;
        for(int i=0;i<=9;++i){
            if(trie[u][i]!=0) {
                f=true;
                break;
            }
        }
        return f;
    }
    void Clear(){
        memset(trie,0,sizeof trie);
        memset(book,0,sizeof book);
        tot=0;
    }
}test;
string str;

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        test.Clear();
        scanf("%d",&n);
        bool ans=false;
        for(int i=1;i<=n;++i){
            cin>>str;
            if(test.Insert(str)){
                ans=true;
            }
        }
        if(ans) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

 
 

ac自动机

kmp是单模式串匹配，ac自动机可以跑多模式串匹配。
ac自动机是在trie树上增加fail指针，用来实现当前节点失配时，跳转到前缀与已匹配部分相同后缀相同的节点上。
Fail指针的实质含义就是：如果一个点i的Fail指针指向j。那么root到j的字符串是root到i的字符串的一个后缀。

举个栗子：

i:4 j:7
root到i的字符串是“ABC”
root到j的字符串是“BC”
“BC”是“ABC”的一个后缀
所以i的Fail指针指向j

查询时：从头开始遍历文本串，对于文本串上的每个字母，不停地在树上找前缀与当前已匹配部分的后缀相同的节点。

学习链接：AC自动机讲解超详细 ，AC自动机 算法详解(图解)及模板

ac自动机模板：

const int maxn=5e5+7;
const int N=26;
struct acAutomaton{
    int trie[maxn][N],cntword[maxn],fail[maxn],tot;
    void Clear(){
        memset(trie,0,sizeof trie);
        memset(cntword,0,sizeof cntword);
        memset(fail,0,sizeof fail);
        tot=0;
    }
    //创建字典树
    void insertWord(string str){
        int u=0;
        for(int i=0;i<str.length();++i){
            int v=str[i]-'a';
            if(trie[u][v]==0){
                trie[u][v]=++tot;
            }
            u=trie[u][v];
        }
        ++cntword[u];
    }
    void getFail(){
        queue<int> q;
        //将根节点存在的子节点扔进队列
        for(int i=0;i<26;++i){
            if(trie[0][i]){
                fail[trie[0][i]]=0;
                q.push(trie[0][i]);
            }
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;++i){
                if(trie[u][i]==0){
        //当前字母没有为i+'a'的子节点，将其子节点指向它fail指针的为i+'a'子节点,(根节点的fail指针指向自己)
        //因为当前后缀和fail的前缀相同，可以共用子节点
                    trie[u][i]=trie[fail[u]][i];
                }
                else {
        //为的i+'a'子节点的fail指针指向父节点fail指针为i+'a'的子节点
                    fail[trie[u][i]]=trie[fail[u]][i];
                    q.push(trie[u][i]);
                }
            }
        }
    }
    int query(string str){
        int u=0,ans=0;
        for(int i=0;i<str.size();++i){
       //对于一个字母，不停地在树上找前缀与当前已匹配部分的后缀相同的节点,但是注意u指针不变
       //当单词被计算过或fail不存在时结束
            u=trie[u][str[i]-'a'];
            for(int j=u;j&&cntword[j]!=-1;j=fail[j]){
                ans+=cntword[j];
                cntword[j]=-1;
            }
        }
        return ans;
    }
}Test;

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

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+7;
struct acAutomaton{
    int trie[maxn][26],cntword[maxn],fail[maxn],tot;
    void Clear(){
        memset(trie,0,sizeof trie);
        memset(cntword,0,sizeof cntword);
        memset(fail,0,sizeof fail);
        tot=0;
    }
    //创建字典树
    void insertWord(string str){
        int u=0;
        for(int i=0;i<str.length();++i){
            int v=str[i]-'a';
            if(trie[u][v]==0){
                trie[u][v]=++tot;
            }
            u=trie[u][v];
        }
        ++cntword[u];
    }
    void getFail(){
        queue<int> q;
        //将根节点存在的子节点扔进队列
        for(int i=0;i<26;++i){
            if(trie[0][i]){
                fail[trie[0][i]]=0;
                q.push(trie[0][i]);
            }
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=0;i<26;++i){
                if(trie[u][i]==0){
        //当前字母没有为i+'a'的子节点，将其子节点指向它fail指针的为i+'a'子节点
        //因为当前后缀和fail的前缀相同
                    trie[u][i]=trie[fail[u]][i];
                }
                else {
        //为的i+'a'子节点的fail指针指向父节点fail指针为i+'a'的子节点
                    fail[trie[u][i]]=trie[fail[u]][i];
                    q.push(trie[u][i]);
                }
            }
        }
    }
    int query(string str){
        int u=0,ans=0;
        for(int i=0;i<str.size();++i){
            //对于一个字母，不停地在树上找与其后缀相同的串
            //当单词被计算过或fail不存在结束
            u=trie[u][str[i]-'a'];
            for(int j=u;j&&cntword[j]!=-1;j=fail[j]){
                ans+=cntword[j];
                cntword[j]=-1;
            }
        }
        return ans;
    }
}Test;
string str;
int main(){
    int n;
    cin>>n;
    Test.Clear();
    for(int i=1;i<=n;++i){
        cin>>str;
        Test.insertWord(str);
    }
    Test.getFail();
    cin>>str;
    cout<<Test.query(str)<<endl;

    return 0;
}