理解题意之后，很自然的想到了用AC自动机搞，结果网上一搜，全是暴搜，按照自己的思想，AC自动机搞起，果然在提交了数次之后，看到了Accept。
AC自动机需要三个步骤：
第一步：建立字典树；
第二步：为字典树建立 Fail 指针 ；
第三步：进行匹配；
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131 |
#include<iostream>#include<string>#include<string.h>#include<cctype>#include<queue>#include<stdio.h>#define max(x,y) ((x) > (y) ? (x) : (y))using
namespace std ;struct
Node { Node *next[26] ; Node *fail ; bool
is_over ; int
len ;};Node* new_node() { Node *root = new
Node ; root ->fail = NULL ; for(int
i = 0 ; i< 26 ; i++) root->next[i] = NULL ; root ->is_over = false
; return
root ;}void
build_tree( Node *root , char
*s ) { int
len = strlen(s) ; for(int
i = 0 ; i < len ; i++) { if(root->next[s[i] - ‘a‘] == NULL) root->next[s[i] - ‘a‘] = new_node() ; root = root ->next[s[i] - ‘a‘] ; } root ->is_over = true
; root ->len = len ;}void
build_fail(Node *root) { Node *r = root ; queue< Node* > q ; q.push(root) ; while(!q.empty()) { r = q.front() ; q.pop() ; Node *p = r ; for(int
i = 0 ; i < 26 ; i++) { if(p->next[i] != NULL) { if(p == root) { p->next[i]->fail = root ; q.push(p->next[i]) ; continue
; } while(r->fail->next[i] == NULL && r ->fail != root) r = r->fail ; if(r->fail ->next[i] != NULL) p ->next[i]->fail = r ->fail ->next[i] ; else p ->next[i] ->fail = root ; q.push(p->next[i]) ; } } }}int
A_C(Node *root , char
*s) { int
len = strlen(s) ; Node *r = root ; int
count = 0 ; for(int
i = 0 ; i < len ; i++) { if(!isalpha(s[i])) continue
; if(r->next[s[i]-‘a‘] != NULL) { r = r ->next[s[i]-‘a‘] ; if(r->is_over && !(islower(s[i+1])) && !(islower(s[i - r->len])) ) count++ ; } else
{ while(r->next[s[i]-‘a‘] == NULL && r != root ) r = r ->fail ; if(r ->next[s[i] - ‘a‘] != NULL) r = r ->next[s[i] - ‘a‘] ; else r = root ; if(r->is_over && (!(isalpha(s[i+1])) ) && !(islower(s[i - r->len])) ) count++ ; } } return
count ;}int
main() { int
n , m ; int
t = 1 ; while(scanf("%d%d",&n,&m) == 2) { Node *root = new_node() ; Node *r = root ; while(n--) { char
s[30] ; scanf("%s",&s) ; getchar() ; build_tree(root,s) ; root = r ; } r->fail = NULL ; root = r ; build_fail(r) ; char
str[30][100] ; char
str1[30][100] ; int
count[30] = {0} ; int
ma = 0 ; for(int
i = 0 ; i < m ; i++) { gets(str[i]) ; strcpy(str1[i],str[i]) ; int
len = strlen(str[i]) ; for(int
j = 0 ; j < len ; j++) if(isupper(str[i][j])) str[i][j] += 32 ; count[i] = A_C(root,str[i]) ; ma = max(ma,count[i]) ; } cout << "Excuse Set #"
<< t++ << endl; for(int
k = 0 ; k < m ; k++) if(count[k] == ma) cout << str1[k] << endl ; cout << endl ; } return
0 ;} |
原文：http://www.cnblogs.com/scottding/p/3656338.html