这是一道简单的AC自动机模版题。
用于检测正确性以及算法常数。
为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。
给定n个模式串和1个文本串,求有多少个模式串在文本串里出现过。
输入格式:
第一行一个n,表示模式串个数;
下面n行每行一个模式串;
下面一行一个文本串。
输出格式:
一个数表示答案
输入样例#1:
2
a
aa
aa
输出样例#1:
2
subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1;
subtask2[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6;
也是模板,没什么么好说的,
只不过每次更新的时候是++,而不是=1!
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
7 #include<map>
8 using namespace std;
9 const int MAXN=1000001;
10 void read(int &n)
11 {
12 char c='+';int x=0;bool flag=0;
13 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
14 while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
15 flag==1?n=-x:n=x;
16 }
17 char s[MAXN];
18 char text[MAXN];
19 int n;
20 int ans=0;
21 struct AC_Automata
22 {
23 int sz;
24 int ch[MAXN][26];//trie树
25 int val[MAXN];// 记录是否有单词
26 int last[MAXN];
27 int f[MAXN];
28 int sigma_sz;
29 void Init()
30 {
31 memset(ch[0],0,sizeof(ch[0]));
32 sz=1;
33 sigma_sz=26;
34 }
35 int idx(char c)
36 {
37 return c-'a';
38 }
39 void Insert(char *s,int pos)
40 {
41 int l=strlen(s); int now=0;
42 for(int i=0;i<l;i++)
43 {
44 int c=idx(s[i]);
45 if(!ch[now][c])
46 {
47 memset(ch[sz],0,sizeof(ch[sz]));
48 val[sz]=0;
49 ch[now][c]=sz++;
50 }
51 now=ch[now][c];
52 }
53 val[now]++;//一个单词的结束
54 }
55 void getfail()
56 {
57 f[0]=0;
58 queue<int>q;
59 for(int i=0;i<sigma_sz;i++)
60 {
61 int u=ch[0][i];
62 if(u)// 此处有单词出现
63 {
64 f[u]=0;// 连向根节点
65 q.push(u);
66 last[u]=0;// 上一个出现的单词一定是根节点
67 // 上面两条语句没什么卵用,只是为了帮助理解AC自动机的含义
68 }
69 }
70 while(!q.empty())
71 {
72 int p=q.front();q.pop();
73 for(int i=0;i<sigma_sz;i++)
74 {
75 int u=ch[p][i];
76 if(!u)//没有孩子
77 {
78 ch[p][i]=ch[f[p]][i];// 补上一条不存在的边,减少查找次数
79 continue;
80 }
81 q.push(u);
82 int v=f[p];// 找到它的失陪指针
83 f[u]=ch[v][i];//因为我们在上面补上了一条不存在边,所以他一定存在孩子
84 last[u]=val[f[u]] ? f[u] : last[f[u]];
85 //判断下是不是单词结尾 是, 不是
86 }
87 }
88 }
89 int ok(int pos)
90 {
91 if(val[pos])
92 {
93 ans+=val[pos];
94 val[pos]=0;
95 ok(last[pos]);
96 }
97 }
98 void find(char *s)// 查找模式串
99 {
100 int l=strlen(s);
101 int j=0;// 当前节点的编号
102 for(int i=0;i<l;i++)
103 {
104 int c=idx(s[i]);
105 while(j&&!ch[j][c])
106 j=f[j];// 顺着失配边走
107 j=ch[j][c]; // 取到儿子
108 if(val[j])
109 ok(j);// 找到一个单词
110 else if(last[j])
111 ok(last[j]);// 当前节点不行就看看上一个单词出现的位置行不行
112 }
113 }
114 }ac;
115 int main()
116 {
117 scanf("%d",&n);
118 ac.Init();
119 for(int i=1;i<=n;i++)
120 {
121 scanf("%s",s);
122 ac.Insert(s,i);
123 }
124 ac.getfail();
125 scanf("%s",text);
126 ac.find(text);
127 printf("%d\n",ans);
128 return 0;
129 }