关键字查询

【题目描述】

每次给你一篇文章，和一些关键字，需要你告诉我多少关键字将匹配于文章。

【输入描述】

第一行包含一个整数，表示有多少篇文章。

每一种情况下都会包含1个整数，表示关键词和关键词的数量，不超过10000。

每个关键词只包含字符'a'~'z'，和长度将不超过50。

最后一行是文章，长度不超过1000000。

【输出描述】

输出文章中包含多少关键字。

【输入样例】

she

say

shr

her

yasherhs

【输出样例】

源代码：

#include<cstdio>
#include<cstring> //包含 strlen()。
int n,num,ans,i[500001][27],over[500001],point[500001],q[500001];
bool mark[500001]; //标记是否已被访问过，除去冗余。
char s[51],sss[1000001]; //节省空间。
void ins() //建立Trie树。
{
    int now=1,length=strlen(s); //now表示父节点的编号。
    for (int a=0;a<length;a++) //在C++中 char[] 从0开始储存。
    {
        int t=s[a]-'a'+1; //将 'a'-'z' 转化为 1-26 方便表示与计算。
        if (i[now][t]) //查询儿子们中是否存在这个字母。
          now=i[now][t]; //若存在，就以这个儿子为父节点，继续建树。
        else
          now=i[now][t]=++num; //若不存在，就赋给这个新儿子以新的编号，然后以它为父亲，继续建树。
    }
    over[now]++; //标记此处为单词结束位置。
}
void acmach() //建立失败指针。
{
    int t=0,w=1,now; //变量t表示当前处理的节点在q[]队列中的编号，变量w表示增加的节点在q[]队列中的编号。
    q[0]=1; //设置边界。
    point[1]=0; //设置边界。
    while (t<w) //若 t>=w 则队列已尽。
    {
        now=q[t++]; //以当前队列中的此元素为父节点进行处理。
        for (int a=1;a<=26;a++) //查询哪些字母是它的儿子。
        {
            if (!i[now][a]) 
              continue;
            int k=point[now]; //前缀（父节点）相同，就看看它们自己相不相同。
            while (!i[k][a]) //匹配不成功，就换个父节点指针。
              k=point[k];
            point[i[now][a]]=i[k][a]; //失败指针储存着匹配成功的节点编号。
            q[w++]=i[now][a]; //当前节点入队。
        }
    }
}
void solve() //查询。
{
    int k=1,length=strlen(sss); //跟上文中变量now的作用相类似。
    for (int a=0;a<length;a++)
    {
        mark[k]=1; //进行标记，此节点在上个循环中已被查询过。
        int t=sss[a]-'a'+1;
        while (!i[k][t]) //若此父节点无此儿子，进行失败指针的跳跃。
          k=point[k];
        k=i[k][t]; //匹配成功的节点的编号。
        if (!mark[k]) //判断是否查找过。
          for (int b=k;b;b=point[b]) //匹配成功了，就查询有没有包含于此前缀的单词。
          {
              ans+=over[b]; //增加单词数。
              over[b]=0; //清空，避免重复增加。
          }
    }
    printf("%d
",ans); //输出答案。
}
int main() //Aho-Croasick自动机。
{
    scanf("%d",&n);
    for (int a=1;a<=n;a++)
    {
        int m;
        num=1;
        ans=0; //初始化。
        for (int b=1;b<=26;b++)
          i[0][b]=1; //设置边界。
        scanf("%d",&m);
        for (int b=1;b<=m;b++)
        {
            scanf("%s",s);
            ins();
        }
        acmach();
        scanf("%s",sss);
        solve();
        for (int b=1;b<=num;b++) //重新初始化，为下一组测试数据做准备。
        {
            point[b]=over[b]=mark[b]=0;
            for (int c=1;c<=26;c++)
              i[b][c]=0;
        }
    }
    return 0;
}