hdu 1251 统计难题 trie

缘起

【1】中给出了trie树这种数据结构并且给出了相应的算法，所以一定要找个板题测一下算法有没有bug. 遂找到了 hdu 1251 统计难题 练手.

分析

题意很裸

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
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀). 

【输入】
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串. 

注意:本题只有一组测试数据,处理到文件结束. 

【输出】
对于每个提问,给出以该字符串为前缀的单词的数量. 

【样例输入】
banana
band
bee
absolute
acm

ba
b
band
abc

【样例输出】
2
3
1
0

【限制】
Time limit 2000 ms
Memory limit 65535 kB

显然用trie爆之即可.

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
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL


const int SIZE = 26;

typedef struct TrieNode
{
	int ch, cnt; // cnt是以到当前节点位置的字符串为前缀的单词的个数
	TrieNode *next[SIZE];
	TrieNode(int ch=0):ch(ch),cnt(1) {memset(next, 0, sizeof(next));}
}TrieNode,*Trie;

void init(Trie &root) {root = new TrieNode;}

int insert(Trie root, char *key, int flag) // flag为0表示建树阶段，此时会插入新的节点, flag为1表示后续回答询问阶段,此时已经不再会新建新的节点
{
	Trie p = root;
	int i = 0;
	while(key[i])
	{
		if (p->next[key[i]-'a'])
		{
			if (!flag) // 如果是建树阶段, 则访问次数+1
			{
				p->next[key[i]-'a']->cnt++; // 如果存在的话, 则此节点的访问次数+1
			} // 如果是询问阶段，就什么也不做, 单纯跳到下一个字符去
		}
		else // 如果不存在, 则要区分是建树阶段还是询问阶段
		{
			if (!flag) p->next[key[i]-'a'] = new TrieNode(key[i]); // 如果是建树阶段,则新建一个节点(这个节点的访问次数默认就是1——因为已经来过了嘛~)
			else return 0;
		}
		p = p->next[key[i++]-'a']; // 来到下一个节点
	}
	return p->cnt;
}

void del(Trie &root)
{
	if (!root) return;
	for (int i = 0; i<SIZE; i++)del(root->next[i]);
	delete root;
	root = 0;
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	Trie root = 0;
	init(root);
	char key[400005];
	while(gets(key), key[0]) insert(root, key,0); // 建树
	while(gets(key)) printf("%d\n", insert(root, key, 1)); // 读取后面的行
	del(root);
	return 0;
}

ac情况

Status Accepted
Time 202ms
Memory 45668kB
Length 1245
Lang C++
Submitted 2019-07-21 22:04:14
Shared
RemoteRunId 29808722

参考

【1】https://yfsyfs.github.io/2019/07/21/%E6%A0%87%E5%87%86trie%E6%A0%91%E5%BA%94%E7%94%A8%E4%B9%8B%E4%B8%B2%E7%9A%84%E5%BF%AB%E9%80%9F%E6%A3%80%E7%B4%A2/