关键词匹配（Ac自动机模板题）

2023-02-24 08:25:55

2772: 关键词匹配

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 10 Solved: 4
[Submit][Status][Web Board]

Description

给你N个单词，然后给定一个字符串，问一共有多少单词在这个字符串中出现过（输入相同的字符串算不同的单词，同一个单词重复出现只计一次）。

Input

第一行一个整数N，表示给定单词的个数。
接下来N行，每行输入一个长度不超过50且全由小写字母组成的单词。
最后一行输入一个长度不超过1000000的字符串。
N≤10000

Output

输出一行包含一个整数，表示共在给定字符串中出现过的单词个数。

Sample Input

5

she

he

say

shr

her

yasherhs

Sample Output

HINT

Source

题解：

　　裸Ac自动机，不会的可以去看看这个博客：http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html；

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define maxn 1000005

 #define maxm 1000005

 using namespace std;

 int n,tot,head,tail,son[maxm][],fai[maxm],sum[maxm],list[maxm];

 char s[maxn];

 void clear(){

         tot=;

         memset(son,,sizeof(son));

         memset(sum,,sizeof(sum));

     }

     void insert(char *s){

         int p=;

         for (int i=;s[i];p=son[p][s[i]-'a'],i++) if (!son[p][s[i]-'a']) son[p][s[i]-'a']=++tot;

         sum[p]++;

     }

     void failed(){

         head=,tail=,list[]=,fai[]=-;

         while (head!=tail){

             int x=list[++head];

             for (int ch=;ch<;ch++)

                 if (son[x][ch]){

                     list[++tail]=son[x][ch];

                     int p=fai[x];

                     while (p!=-&&!son[p][ch]) p=fai[p];

                     if (p==-) fai[son[x][ch]]=;

                     else fai[son[x][ch]]=son[p][ch];

                 }

         }

     }

     void work(char *s){

         int ans=;

         for (int i=,p=;s[i];i++){

             while (p&&!son[p][s[i]-'a']) p=fai[p];

             p=son[p][s[i]-'a'];

             for (int t=p;t;t=fai[t]) ans+=sum[t],sum[t]=;

         }

         printf("%d\n",ans);

     }

 int main()

 {

         cin>>n;//,clear();

         for (int i=;i<=n;i++) scanf("%s",s+),insert(s);

         failed();

         scanf("%s",s+),work(s);

     return ;

 }

码农公寓