文章目錄
AC自动机作为多模式匹配的经典方法，在关键词过滤中有重要应用，在我看来，AC自动机主要是这样几个步骤，第一步是先建立关键词的trie数，第二步是构建自动机，建立关键词之间的联系，第三步是利用第二步构建的自动机进行检索。HDU2222-关键词搜索是AC自动机的一个简单应用。关于AC自动机的资料，可以看这里http://www.notonlysuccess.com/index.php/aho-corasick-automaton/.
问题描述
现在，搜索引擎如谷歌，百度等已经走进每个人的生活。
Wiskey也想在他的图片检索系统中实现这个功能。
每一张图片有一段描述，当用户输入关键字查找图片时，系统会将这些关键字与图片的描述进行匹配，然后显示与这些关键字最匹配的图片。
为了简化用题，这里给你出一段图片的描述，和一些关键字，请你告诉我将匹配多少个关键字。
输入
第一行是一个整数，它的意思是有多少个测试用例。
每一个测试用例包含整数N，它的意思是有多少个关键字。(N <= 10000)
每一个关键字是由’a’-‘z’的字符组成，长度不超过50.
用例的最后一行是描述，长度不超过1000000.
示例输入
1
5
she
he
say
shr
her
yasherhs
示例输出
3
解法：
AC自动机的简单应用。有一个坑是，输入中关键词存在重复时，要计算多次。
代码如下
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
| #include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int NUM = 26;
struct NODE {
int cnt;
NODE *fail;
NODE *next[NUM];
NODE () {
cnt = 0;
fail = NULL;
memset(next, 0, sizeof(next));
}
};
void insert(NODE *root, char *s) {
NODE *cur = root;
while (*s) {
int index = *s - 'a';
if (!cur->next[index]) {
cur->next[index] = new NODE();
}
cur = cur->next[index];
s++;
}
cur->cnt++;
}
void ac_build(NODE *root) {
queue <NODE *> q;
NODE *cur;
root->fail = NULL;
for (int i = 0; i < NUM; i++) {
if (root->next[i]) {
root->next[i]->fail = root;
q.push(root->next[i]);
}
}
while (!q.empty()) {
cur = q.front();
q.pop();
for (int i = 0; i < NUM; i++) {
if (cur->next[i]) {
q.push(cur->next[i]);
NODE *temp = cur->fail;
while (temp) {
if (temp->next[i]) {
cur->next[i]->fail = temp->next[i];
break;
}
temp = temp->fail;
}
if (temp == NULL) {
cur->next[i]->fail = root;
}
}
}
}
}
int ac_find(NODE *root, char *s) {
int sum = 0;
NODE *cur = root;
while (*s) {
int index = *s - 'a';
while (cur->next[index] == NULL && cur != root) {
cur = cur->fail;
}
cur = (cur->next[index] == NULL) ? root : cur->next[index];
NODE *temp = cur;
while (temp != root && temp->cnt != -1) {
sum += temp->cnt;
temp->cnt = -1;
temp = temp->fail;
}
s++;
}
return sum;
}
int main() {
int ncase, n;
char word[51];
char desc[1000001];
scanf("%d", &ncase);
while (ncase--) {
NODE *root = new NODE();
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%s", word);
insert(root, word);
}
scanf("%s", desc);
ac_build(root);
int res = ac_find(root, desc);
printf("%d\n", res);
}
return 0;
}
|
