这是一道水题

给定几个特征串和几个字符串，求每个字符串中有那几个特征码

思路：

把每个特征串放到 TRIE 树里（上），用 AC 机挂着每个串跑一遍即可。但是会出现一种情况：若 B 串为 A 串子串，则可能出现没有匹配到 B 串的情况。比如 ABCD 和 BC，如果用不加修饰的 AC 机跑，会直接把 ABCD 匹配了，而 BC 在 TRIE 树的另一个分支上，没有访问。所以有 3 个解决办法：

1. 在建树前用 strstr 确定每个串是否为另一个串的子串（O（N⁴）TLE）。因此改成 KMP，复杂度 O(N³)，然而代码量很大。

注意到方案 1 使用的 KMP 实际上是对 TRIE 树每个树枝进行匹配，由此不难想到：

2. 在建树时递归沿着 FAIL 指针向树根寻找，如果 FAIL 指针指向的节点为一个特征串的结尾，则将此特征添加到原节点。使用 vector 可以通过此题。

3. 注意到题目时间限制比较宽松，因此可以在 AC 自动机每寻找到一个节点时递归 FAIL 指针，操作通方案 2.

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

#define CHN 129
#define MX 100000
#define MXL 201
#define MXT 10001
#define KJ 32

char vir[MXL];
char web[MXT];
char data[MX];
int flag[MX];
int fail[MX];
int son[MX][CHN];
int ans[501];
int dep[100000];
int nnum;
int root=0;

void insrt(char *str,int len,int index)
{
    int now=root;
    for(int i=0;i<len;i++)
    {
        if(son[now][str[i]-KJ])
        {
            now=son[now][str[i]-KJ];
        }
        else
        {
            nnum++;
            data[nnum]=str[i];
            son[now][str[i]-KJ]=nnum;
            now=nnum;
        }
    }
    flag[now]=index;
}

int q[MXT];
int h,t;

void getfail()
{
    int now,p;
    h=t=0;
    q[0]=root;
    while(h>=t)
    {
        now=q[t];
        for(int i=0;i<CHN;i++)
        {
            if(son[now][i])
            {
                p=fail[now];
                while(p&&!son[p][i]){p=fail[p];}
                fail[son[now][i]]=(son[p][i]==son[now][i]?root:son[p][i]);
                q[++h]=son[now][i];
            }
        }
        t++;
    }
}

void query(char *str,int len)
{
    memset(ans,0,sizeof(ans));
    int now=root;
    for(int i=0;i<len;i++)
    {
        while(son[now][str[i]-KJ]==0&&now!=0)now=fail[now];
        if(flag[now])ans[flag[now]]++;
        now=son[now][str[i]-KJ];
        for(int tmp=now;tmp>0;tmp=fail[tmp])if(flag[tmp])ans[flag[tmp]]++;
    }
}

int main()
{
    int vnum,tnum,flg,totn=0;
    scanf("%d",&vnum);
    for(int i=1; i<=vnum; i++)
    {
        scanf("%s",vir);
        insrt(vir,strlen(vir),i);
    }
    getfail();
    scanf("%d",&tnum);
    for(int i=1; i<=tnum; i++)
    {
        scanf("%s",web);
        query(web,strlen(web));
        flg=0;
        for(int k=1; k<=vnum; k++)

        {
            if(ans[k])
            {
                if(flg==0)
                {
                    flg=1;
                    printf("web %d: %d",i,k);
                }
                else printf(" %d",k);
            }
        }
        if(flg==1)
        {
            puts("");
            totn++;
        }
    }
    printf("total: %d\n",totn);
    return 0;
}