字典树，AC自动机

字典树
概述：给定n个字符串，进行m次询问，每次询问给一个字符串t，问在n个字符串里有几个是字符串t的前缀.
思路：字典树，每个点记一下，以这个点结尾的字符串有几个，查询的时候，一边走，一遍加.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e6+10;
const int maxxn=1e6+10;
struct node{
    int end;
    int a[26];
}trie[maxxn];
int tot=1;
void insert(char *str){
    int len=strlen(str),p=1;
    for(int k=0;k<len;k++){
        int ch=str[k]-'a';
        if(trie[p].a[ch]==0)
            trie[p].a[ch]=++tot;
        p=trie[p].a[ch];
    }
    trie[p].end++;
}
int search(char *str){
    int len=strlen(str),p=1,res=0;
    for(int k=0;k<len;k++){
        p=trie[p].a[str[k]-'a'];
        res+=trie[p].end;
        if(p==0)    break;
    }
    return res;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    char s[maxn];
    for(int i=0;i<n;i++){
        scanf("%s",s);
        insert(s);
    }
    for(int i=0;i<m;i++){
        scanf("%s",s);
        printf("%d\n",search(s));
    }
    return 0;
} 

AC自动机
AC自动机能解决单个母串，多个子串的问题，例如某一个子串出现了多少次，一共出现了几个子串等等.
简单来说为三步
1.建立子串的字典树
2建立fail指针，从而添加失败路径
3.跑母串
https://blog.csdn.net/bestsort/article/details/82947639?utm_medium=distribute.pc_relevant.none-task-blog-OPENSEARCH-1.control&dist_request_id=&depth_1-utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-1.control
有N个由小写字母组成的模式串以及一个文本串T。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TT中出现的次数最多。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1000010;
int trie[maxn][26];
int fail[maxn];
int sum[maxn];
char str1[200][100];
char str2[maxn];
int tot=0,eend[maxn],ans[200];
void init(void){
    memset(trie,0,sizeof(trie));
    memset(fail,0,sizeof(fail));
    memset(sum,0,sizeof(sum));
    memset(eend,0,sizeof(eend));
    memset(ans,0,sizeof(ans));
    tot=0;
}
//建立字典树
void _insert(int a){
    int p=0,k,len=strlen(str1[a]);
    for(int i=0;i<len;i++){
        k=str1[a][i]-'a';
        if(!trie[p][k]) trie[p][k]=++tot;
        p=trie[p][k];
    }
    sum[p]=1;
    eend[p]=a;
}
//获得每个点的fail值
void getfail(void){
    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.size()){
        int p;
        int now=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            p=trie[now][i];
            if(p)    fail[p]=trie[fail[now]][i],q.push(p);
            else trie[now][i]=trie[fail[now]][i]; //如果这个点不存在就直接将这个点的编号设为其上一个点fail指针指向的点的下一个
        }
    }
}
//查找
void _search(){
    int p=0,k,len=strlen(str2);
    for(int i=0;i<len;i++){
        k=str2[i]-'a';
        p=trie[p][k];
        for(int j=p;j;j=fail[j])
            ans[eend[j]]+=sum[j];
    }
    return ;
}
int main(void){
        int n;
        while(scanf("%d",&n),n){
            init();
            for(int i=1;i<=n;i++){
                scanf("%s",str1[i]);
                _insert(i);
            }
            getfail();
            scanf("%s",str2);
            _search();
            int maxx=-1;
            for(int i=1;i<=n;i++)
                maxx=max(maxx,ans[i]);
            printf("%d\n",maxx);
            for(int i=1;i<=n;i++){
                if(ans[i]==maxx)
                printf("%s\n",str1[i]);
            }
        }
        return 0;
}

fail树的写法下次再写