https://loj.ac/problem/10057

题目描述

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

思路

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

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

??接下来就是匹配时的处理，我们类似\(KMP\)，需要处理出一个\(next\)数组，表示在当前位置失配后跳转的位置。我们考虑\(next\)数组的具体意义：由于匹配是在\(trie\)树上进行的，我们假设当前节点为\(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\)都具有相同的转移边，那么\(next[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;
}

玄武密码

原文：https://www.cnblogs.com/fangbozhen/p/11794514.html