Keywords Search

https://loj.ac/problem/10057

题目描述

  给出n个字符串和一篇文章,求这几个单词在文章中出现过多少个。

思路

  多字符串的匹配问题,显然可以用AC自动机做。就先介绍一下AC自动机。AC主要可以包括两个内容:字典树和KMP。

  首先我们对所有待匹配的建一棵字典树。

  接下来就是匹配时的处理,我们类似KMP,需要处理出一个next数组,表示在当前位置失配后跳转的位置。我们考虑next数组的具体意义:由于匹配是在tried树上进行的,我们假设当前节点为u,代表着字典树上一段字符串的前缀T[1..j],也就是主串中的S[i-j+1..i],显然如果能够继续匹配,就继续;否则,我们要找到另一个一字典树上的前缀满足T’[1...k]=S[i-k+1..i]。由此知这个next数组只与字典树本身有关,我们可以直接预处理出这个数组。

  考虑如何建立next数组,与KMP类似,假设我们现在有两个节点u、v,并且满足next[u]=v。如果u和v都具有相同的转移边,那么nxt[u的下一个节点]=v下一个节点;而如果转移边不同,我们考虑类似KMP,不断使v=next[v],知道可以匹配为止。不过我们在建立next数组时可以在假如一个优化:如果不存在ch[u][i],我们可以直接令ch[u][i]=ch[nxt[u]][i],这显然是对的,因为不存在使我们也会按next往前跳。

  而这道题中还有一点要注意,我们记录的是出现多少单词数,因此匹配完后我们可以“删去”这个节点,即将ed标记设为0。

 代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
char s[1000010];
int ch[MAXN][27],nxt[MAXN],tot,ans,ed[MAXN];
void clear()
{
    memset(ch,0,sizeof(ch));
    memset(ed,0,sizeof(ed));
    tot=1;ans=0;
    for(int i=0;i<26;i++)
        ch[0][i]=1,ch[1][i]=0;
}
void insert(char *s)
{
    int u=1,len=strlen(s);
    for(int i=0;i<len;i++)
    {
        int c=s[i]-'a';
        if(!ch[u][c])ch[u][c]=++tot;
        u=ch[u][c];
    }
    ed[u]++;
}
void bfs()
{
    queue<int>q;
    for(int i=0;i<26;i++)
        ch[0][i]=1;
    q.push(1);nxt[1]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=0;i<26;i++)
        {
            if(!ch[u][i])ch[u][i]=ch[nxt[u]][i];
            else
            {
                q.push(ch[u][i]);
                int v=nxt[u];
                nxt[ch[u][i]]=ch[v][i];
            }
        }
    }
}
void find(char *s)
{
    int u=1,len=strlen(s);
    for(int i=0;i<len;i++)
    {
        int c=s[i]-'a';
        int k=ch[u][c];
        while(k>1)
        {
            ans+=ed[k];
            ed[k]=0;
            k=nxt[k];
        }
        u=ch[u][c];
    }
}
int main() 
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf(" %s",s);
            insert(s);
        }
        bfs();
        scanf(" %s",s);
        find(s);
        printf("%d\n",ans);
    }
    return 0;
}

 

上一篇:linux-如何使用ed在最后一个模式机之后添加文本


下一篇:finereport 通过条件弹出 alert进行提示