hdu 2222 Keywords Search ac自动机板题

缘起

【1】中已经极为初步的介绍了ac自动机这种数据结构. 并且给出了板子. 那么自然需要验证一下板子的正确性. hdu 2222 Keywords Search

分析

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
第一行输入测试数据的组数，然后输入一个整数n，接下来的n行每行输入一个单词，
最后输入一个字符串，问在这个字符串中有多少个单词出现过。

【输入】
多样例. 第一行是样例数. 每个样例包含一个正整数N表示模式串的数量，然后是N个模式串. 样例最后一个单词是
文本串。单词都是小写字母. 而且模式串的长度<=50,  文本串的长度<=1000000

【输出】
对于每个样例，输出多少单词出现过.

【样例输入】
1
5
she
he
say
shr
her
yasherhs

【样例输出】
3

【限制】
1s

其实就是【1】中处理的问题. 现在兑现【1】中承诺的板子.

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL

const int SIZE = 26;
char s[1000005], t[55];

struct AcNode
{
	AcNode *fail, *next[SIZE];
	char c;
	int cnt; // cnt是业务域,表示以此节点为终点的模式串的数量
	AcNode():fail(0),cnt(0){memset(next, 0, sizeof(next));}
} *root;

void insert() // 构建标准trie, 这没什么好说的，参见【2】即可.
{
	int i = 0;
	AcNode *p = root;
	while(t[i])
	{
		if (!p->next[t[i]-'a'])
		{
			p->next[t[i]-'a'] = new AcNode;
			p->next[t[i]-'a']->c = t[i];
		}
		p = p->next[t[i]-'a'];
		++i;
	}
	p->cnt++;
}

void makefail() // bfs（确切讲其实是层序遍历）制作fail指针
{
	queue<AcNode *>q;
	for (int i = 0; i<SIZE; i++)
	{
		if (root->next[i])
		{
			root->next[i]->fail = root; // 根据fail的定义, 不难知道这是正确的, 因为root的第一层孩子互异
			q.push(root->next[i]); // 制作完fail指针就塞进队列, 因为后面的孩子要用
		}
	}
	while(!q.empty())
	{
		AcNode *front = q.front();
		q.pop();
		for (int i = 0; i<SIZE; i++)
		{
			if (front->next[i])
			{
				AcNode *f = front->fail;
				while (f!=root && !f->next[i])
				{
					f = f->fail;
				} // 要么f变成root, 要么f使得f->next[i]存在, 但是有可能两者兼得, 两者兼得的时候根据fail的定义, 应该取值为f->next[i]而不是root
				front->next[i]->fail = f->next[i]?f->next[i]:root; 
				q.push(front->next[i]); // 制作完毕fail指针就塞进队列
			}
		}
	}
}

int query()
{
	int ans = 0, i = 0;
	AcNode *p = root, *tmp;
	while(s[i])
	{
		while(p!=root && !p->next[s[i]-'a'])
		{
			p = p->fail;
		} // 失配之后, fail跳转,直至找到潜在root或者潜在的匹配者（即找到了匹配）
		p = p->next[s[i]-'a']?p->next[s[i]-'a']:root; // 同makefail中的理由
		tmp = p;
		while(tmp!=root && ~tmp->cnt) // 开始统计
		{
			ans+=tmp->cnt; // tmp->cnt可能为0,加也白加
			tmp->cnt = -1;  // 防止重复统计
			tmp = tmp->fail;
		}
		++i;
	}
	return ans;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase,n;
	scanf("%d", &kase);
	while (kase--)
	{
		root = new AcNode;
		scanf("%d", &n);
		while(n--)
		{
			scanf("%s", t);
			insert();
		}
		makefail();
		scanf("%s", s);
		printf("%d\n",query());
	}
	return 0;
}

注意，为什么上面query方法中p不需要移动，而仅仅拜托tmp去移动. 这是因为p要保持最长, 然后让tmp去移动匹配那些较短的. 这就是ac自动机匹配的过程——p保持最长的那一个，然后tmp根据fail去跳找到较短的那些匹配.

ac情况

Status Accepted
Time 343ms
Memory 56880kB
Length 1629
Lang G++
Submitted 2019-10-14 16:59:02
Shared
RemoteRunId 30916138

参考

【1】https://yfsyfs.github.io/2019/10/11/ac%E8%87%AA%E5%8A%A8%E6%9C%BA%E5%AD%A6%E4%B9%A0/