洛谷P3808 【模板】AC自动机（简单版）

题目背景

这是一道简单的AC自动机模板题。

用于检测正确性以及算法常数。

为了防止卡OJ，在保证正确的基础上只有两组数据，请不要恶意提交。

管理员提示：本题数据内有重复的单词，且重复单词应该计算多次，请各位注意

题目描述

给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。

输入输出格式

输入格式：

第一行一个n，表示模式串个数；

下面n行每行一个模式串；

下面一行一个文本串。

输出格式：

一个数表示答案

输入输出样例

输入样例#1：

2
a
aa
aa

输出样例#1：

说明

subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1；

subtask2[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6；

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 long long read()
 6 {
 7     long long x=0,f=1;
 8     char ch=getchar();
 9     while(ch>'9'||ch<'0')
10     {
11         if(ch=='-')
12             f=-1;
13         ch=getchar();
14     }
15     while(ch>='0'&&ch<='9')
16     {
17         x=x*10+ch-'0';
18         ch=getchar();
19     }
20     return x*f;
21 }
22 const int maxn=1e6+10;
23 char mob[maxn];
24 int q[maxn];
25 int n,cnt;
26 struct node
27 {
28     int fail,num;
29     int ch[30];
30 } t[maxn];
31 void insert()
32 {
33     int len=strlen(mob),u=0;
34     for(int i=0; i<len; i++)
35     {
36         int s=mob[i]-'a';
37         if(t[u].ch[s]==0)
38             t[u].ch[s]=++cnt;
39         u=t[u].ch[s];
40     }
41     t[u].num++;
42 }
43 void getfail()
44 {
45     int l=0,r=0;
46     for(int i=0; i<26; i++)
47         if(t[0].ch[i]!=0)
48         {
49             t[t[0].ch[i]].fail=0;
50             q[++r]=t[0].ch[i];
51         }
52     while(l<r)
53     {
54         int u=q[++l];
55         for(int i=0; i<26; i++)
56         {
57             int v=t[u].ch[i];
58             if(v)
59             {
60                 t[v].fail=t[t[u].fail].ch[i];
61                 q[++r]=v;
62             }
63             else
64                 t[u].ch[i]=t[t[u].fail].ch[i];
65         }
66     }
67 }
68 int query()
69 {
70     int len=strlen(mob);
71     int u=0,ans=0;
72     for(int i=0; i<len; i++)
73     {
74         int s=mob[i]-'a';
75         u=t[u].ch[s];
76         int v=u;
77         while(v&&t[v].num!=-1)
78         {
79             ans+=t[v].num;
80             t[v].num=-1;
81             v=t[v].fail;
82         }
83     }
84     return ans;
85 }
86 int main()
87 {
88     n=read();
89     for(int i=1; i<=n; i++)
90     {
91         cin>>mob;
92         insert();
93     }
94     t[0].fail=0;
95     getfail();
96     cin>>mob;
97     printf("%d",query());
98     return 0;
99 }

View Code