这是一道简单的AC自动机模板题。
用于检测正确性以及算法常数。
为了防止卡OJ，在保证正确的基础上只有两组数据，请不要恶意提交。
管理员提示：本题数据内有重复的单词，且重复单词应该计算多次，请各位注意
给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。
输入格式：
第一行一个n，表示模式串个数；
下面n行每行一个模式串；
下面一行一个文本串。
输出格式：
一个数表示答案
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
转载于:https://www.cnblogs.com/liweilin/p/10198643.html
相关资源：JAVA上百实例源码以及开源项目