Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给出 n 个模式串，一个文本串，问文本串中出现了多少个模式串。
思路：AC 自动机裸题。代码风格来自 bin 神。静态数组的写法。
需要理解在 build fail 的时候，先单独处理 root 的必要性。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月16日 星期二 06时00分48秒
4File Name :code/hdu/2222.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <stack>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <deque>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N = 5E5+7;
34int n;
35struct Trie
36{
37 int nxt[N][26],fail[N],end[N];
38 int root,L;
39 int newnode()
40 {
41 for ( int i = 0 ; i < 26 ; i++) nxt[L][i]=-1;
42 end[L++] = 0 ;
43 return L-1;
44 }
45 void init()
46 {
47 L = 0 ;
48 root = newnode();
49 }
50 void Insert(char *s)
51 {
52 int len = strlen(s);
53 int u = root;
54 for ( int i = 0 ; i < len ; i++)
55 {
56 int v = s[i]-'a';
57 if (nxt[u][v]==-1)
58 nxt[u][v] = newnode();
59 u = nxt[u][v];
60 }
61 end[u]++;
62 }
63 void Getfail()
64 {
65 queue<int>Q;
66 fail[root] = root;
67 for ( int i = 0 ; i < 26 ; i++)
68 if (nxt[root][i]==-1)
69 nxt[root][i] = root;
70 else
71 {
72 fail[nxt[root][i]] = root;
73 Q.push(nxt[root][i]);
74 }
75 while (!Q.empty())
76 {
77 int cur = Q.front();
78// cout<<"cur:"<<cur<<endl;
79 Q.pop();
80 for ( int i = 0 ; i < 26 ; i++)
81 if (nxt[cur][i]==-1)
82 nxt[cur][i] = nxt[fail[cur]][i];
83 else
84 {
85 fail[nxt[cur][i]] =nxt[fail[cur]][i];
86 Q.push(nxt[cur][i]);
87 }
88 }
89 }
90 int Search(char *s)
91 {
92 int len = strlen(s);
93 int u = root;
94 int res = 0 ;
95// cout<<"txt:"<<s<<endl;
96 for ( int i = 0 ; i < len; i++)
97 {
98 int v = s[i]-'a';
99 u = nxt[u][v];
100 int tmp = u;
101 while (tmp!=root)
102 {
103 res +=end[tmp];
104 end[tmp] = 0 ;
105 tmp = fail[tmp];
106 }
107 }
108 return res;
109 }
110}ac;
111char s[52];
112char text[1000005];
113int main()
114{
115 #ifndef ONLINE_JUDGE
116 freopen("code/in.txt","r",stdin);
117 #endif
118 int T;
119 cin>>T;
120 while (T--)
121 {
122 scanf("%d",&n);
123 ac.init();
124 for ( int i = 1 ; i <= n ; i++)
125 {
126 scanf("%s",s);
127 ac.Insert(s);
128// cout<<"s:"<<s<<endl;
129 }
130 ac.Getfail();
131 scanf("%s",text);
132// cout<<"txt:"<<text<<endl;
133 printf("%d\n",ac.Search(text));
134 }
135 #ifndef ONLINE_JUDGE
136 fclose(stdin);
137 #endif
138 return 0;
139}讲真，觉得上面的代码写得丑（bin 神的粉丝别打我 T T） 于是自己改成了动态的写法。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月16日 星期二 15时26分42秒
4File Name :code/hdu/r2222.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <stack>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <deque>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33struct Trie
34{
35 struct Node
36 {
37 Node *nxt[26];
38 Node *fail;
39 int cnt;
40 Node()
41 {
42 for ( int i = 0 ; i < 26 ; i++) nxt[i] = NULL;
43 cnt = 0 ;
44 fail=NULL;
45 }
46 };
47 Node *root;
48 void init()
49 {
50 root = new Node();
51 }
52 void Insert(char *s)
53 {
54 int len = strlen(s);
55 Node *u = root;
56 for ( int i = 0 ; i < len ; i++)
57 {
58 int v = s[i]-'a';
59 if (u->nxt[v]==NULL) u->nxt[v] = new Node();
60 u = u->nxt[v];
61 }
62 u->cnt++;
63 }
64 void getFail()
65 {
66 root->fail = root;
67 queue<Node*>Q;
68 for ( int i = 0 ; i < 26 ; i++)
69 {
70 if (root->nxt[i]==NULL)
71 root->nxt[i] = root;
72 else
73 {
74 root->nxt[i]->fail = root;
75 Q.push(root->nxt[i]);
76 }
77 }
78 while (!Q.empty())
79 {
80 Node *cur = Q.front();
81 Q.pop();
82 for ( int i = 0 ; i < 26 ; i++)
83 if (cur->nxt[i]==NULL)
84 {
85 cur->nxt[i] = cur->fail->nxt[i];
86 }
87 else
88 {
89 cur->nxt[i]->fail = cur->fail->nxt[i];
90 Q.push(cur->nxt[i]);
91 }
92 }
93 }
94 int Search(char *s)
95 {
96 int len = strlen(s);
97 Node *u = root;
98 int res = 0 ;
99 for ( int i = 0 ; i < len ; i++)
100 {
101 int v = s[i]-'a';
102 u = u->nxt[v];
103 Node *tmp = u;
104 while (tmp!=root)
105 {
106 res = res + tmp->cnt;
107 tmp->cnt = 0 ;
108 tmp = tmp->fail;
109 }
110 }
111 return res;
112 }
113}ac;
114char text[1000010];
115int n ;
116int main()
117{
118 #ifndef ONLINE_JUDGE
119 freopen("code/in.txt","r",stdin);
120 #endif
121 int T;
122 cin>>T;
123 while (T--)
124 {
125 scanf("%d",&n);
126 ac.init();
127 for ( int i = 1 ; i <= n ; i ++)
128 {
129 scanf("%s",text);
130 ac.Insert(text);
131 }
132 ac.getFail();
133 scanf("%s",text);
134 printf("%d\n",ac.Search(text));
135 }
136 #ifndef ONLINE_JUDGE
137 fclose(stdin);
138 #endif
139 return 0;
140}