【模板】AC自动机（求包含所有子串的子串）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
struct Tree//字典树
{
    int fail;//失配指针
    int vis[26];//子节点的位置
    int end;//标记有几个单词以这个节点结尾
} AC[100005]; //Trie树
int cnt=0;//Trie的指针

inline void Build(string s)
{

    int l=s.length();
    int now=0;//字典树的当前指针
    for(int i=0; i<l; ++i) //构造Trie树
    {
        if(AC[now].vis[s[i]-'a']==0)//Trie树没有这个子节点
        {
            memset(AC[cnt].vis,0,sizeof(AC[cnt].vis));
            AC[cnt].end=0;
            AC[now].vis[s[i]-'a']=cnt++;//构造出来

        }
        now=AC[now].vis[s[i]-'a'];//向下构造
    }
    AC[now].end+=1;//标记单词结尾
}
void Get_fail()//构造fail指针
{
    queue<int> Q;//队列
    for(int i=0; i<26; ++i) //第二层的fail指针提前处理一下
    {
        if(AC[0].vis[i]!=0)
        {
            AC[AC[0].vis[i]].fail=0;//指向根节点
            Q.push(AC[0].vis[i]);//压入队列
        }
    }
    while(!Q.empty())//BFS求fail指针
    {
        int u=Q.front();
        Q.pop();
        for(int i=0; i<26; ++i) //枚举所有子节点
        {
            if(AC[u].vis[i]!=0)//存在这个子节点
            {
                AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
                //子节点的fail指针指向当前节点的
                //fail指针所指向的节点的相同子节点
                Q.push(AC[u].vis[i]);//压入队列
            }
            else//不存在这个子节点
                AC[u].vis[i]=AC[AC[u].fail].vis[i];
            //当前节点的这个子节点指向当
            //前节点fail指针的这个子节点
        }
    }
}
int AC_Query(string p)//AC自动机匹配
{
    int l=p.length();
    int now=0,ans=0;
    for(int i=0; i<l; ++i)
    {
        now=AC[now].vis[p[i]-'a'];//向下一层
        for(int t=now; t&&AC[t].end!=-1; t=AC[t].fail) //循环求解
        {
            ans+=AC[t].end;
            AC[t].end=-1;
        }
    }
    return ans;
}
int main()
{
    int n,t;
    char s[100005];
    char p[100005];
    int maxlen=0;
    scanf("%d",&t);
    while(t--)
    {

        maxlen=0;
        memset(AC[0].vis,0,sizeof(AC[0].vis));
        cnt=1;
        scanf("%d",&n);
        for(int i=1; i<=n; ++i)
        {
            scanf("%s",s);
            int slen=strlen(s);
            if(slen>maxlen)
            {
                maxlen=slen;
                strcpy(p,s);
            }
            Build(s);
        }
        AC[0].fail=0;//结束标志
        Get_fail();//求出失配指针
        if(n==AC_Query(p))
            printf("%s\n",p);
        else
            printf("No\n");
    }
    return 0;
}
/*
3
10
you
better
worse
richer
poorer
sickness
health
death
faithfulness
youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness
5
abc
cde
abcde
abcde
bcde
3
aaaaa
aaaab
aaaac
*/