HDU 2222：Keywords Search(AC自动机判断长串中出现了多少个已知单词)

数据结构

题面链接

• 题意

有t组测试数据，对于每组测试数据
给出N个单词(N <= 10000)，每个单词都只包含小写字母（每个单词的长度不超过50）
接下来给你一个长串s（长度不超过1000000）
问上面的n个单词有多少个在长串s中出现过。

• 样例

Sample Input
1
5
she
he
say
shr
her
yasherhs

Sample Output
3

• 分析

AC自动机的模板题。但是有地方需要注意。
我们AC自动机的模板里面对于单词的标记是出现了就标记为1，这里由于可能出现相同的单词所以会重复去算。所以我们对于isword数组的存值为++。而不是==1.（在代码第21行）同时对于模板的find函数。66行到77行。我们应该标记已经出现的单词，ans加了之后就应该改变isword的值为0，不重复计数。

• 代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=5e5+5;
int last[maxn],f[maxn];
int ch[maxn][26];
int cnt=0;
int isword[maxn];
void insert(char s[])
{
    int root=0;
    int l=strlen(s);
    for(int i=0;i<l;i++)
    {
        if(ch[root][s[i]-'a']==0)
            ch[root][s[i]-'a']=++cnt;
        root=ch[root][s[i]-'a'];
    }
    isword[root]++;
}
void getfail()
{
    queue<int>q;
    f[0]=0;
    for(int i=0;i<26;i++)
    {
        int u=ch[0][i];
        if(u!=0)
        {
            f[u]=0;
            q.push(u);
            last[u]=0;
        }
    }
    while(!q.empty())
    {
        int r=q.front();
        q.pop();
        for(int c=0;c<26;c++)
        {
            int u=ch[r][c];
            if(u==0)
            {
                ch[r][c]=ch[f[r]][c];
                continue;
            }
            q.push(u);
            int v=f[r];
            while(v&&!ch[v][c])
                v=f[v];
            f[u]=ch[v][c];
            last[u]=isword[f[u]]?f[u]:last[f[u]];
        }
    }
}
int find(char T[])
{
    int ans=0;
    int n=strlen(T);
    int j=0;
    for(int i=0;i<n;i++)
    {
        j=ch[j][T[i]-'a'];
        if(isword[j])
        {
            ans+=isword[j];
            isword[j]=0;
        }
        int temp=last[j];
        while(temp)
        {
            ans+=isword[temp];
            isword[temp]=0;
            temp=last[temp];
        }
    }
    return ans;
}
char s[maxn*2];
char s1[10010];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(ch,0,sizeof(ch));
        memset(isword,0,sizeof(isword));
        int n;
        scanf("%d",&n);
        while(n--)
        {
            scanf("%s",s1);
            insert(s1);
        }
        getfail();
        scanf("%s",s);
        printf("%d\n",find(s));
    }
    return 0;
}