Who's Studio.

hihoCoder#1014 - Trie树

Word count: 479Reading time: 2 min
2016/05/11

题目

Trie树就是字典树。对于一个给定的词典，任给一个字符串，输出词典中以该字符串为前缀的单词数目。
具体描述请见hihoCoder。

解题思路

在建立Trie树的同时我们就可以着手统计以某个字符串为前缀的节点个数，即每次添加一个新单词的时候，沿途更新所有经过的节点。

时间复杂度

单词查询用时26M（M：查询字符串的长度），单次插入用时26M。

代码

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
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Node {
	int L = 1;
	char ch = ' ';
	vector<Node*> successors;

	Node(char c) {
		ch = c;
	}
};

class Trie {
private:
	Node* root;

	void updatePrefix(Node* node, string word, int idx) {
		if (idx == word.size())
			return;

		bool find = false;
		for (int i = 0; i < node->successors.size(); i++) {
			if (node->successors[i]->ch == word[idx]) {
				find = true;
				node->successors[i]->L++;
				updatePrefix(node->successors[i], word, idx + 1);
				break;
			}
		}

		if (!find) {
			for (int i = idx; i < word.size(); i++) {
				node->successors.push_back(new Node(word[i]));
				node = node->successors.back();
			}
		}
	}

	int findPrefix(Node* node, string query, int idx) {
		for (int i = 0; i < node->successors.size(); i++) {
			if (node->successors[i]->ch == query[idx]) {
				if (idx == query.size() - 1)
					return node->successors[i]->L;

				return findPrefix(node->successors[i], query, idx + 1);
			}
		}

		return 0;
	}

	void deleteTrie(Node* node) {
		for (int i = 0; i < node->successors.size(); i++)
			deleteTrie(node->successors[i]);
		delete node;
	}
	
public:
	Trie() {
		root = new Node('$');
	}

	~Trie() {
		deleteTrie(root);
	}

	void insert(string word) {
		updatePrefix(root, word, 0);
	}

	int getStat(string query) {
		return findPrefix(root, query, 0);
	}
};

int main() {
	int n = 0;
	cin >> n;
	string* words = new string[n];
	for (int i = 0; i < n; i++)
		cin >> words[i];
	int m = 0;
	cin >> m;
	string* queries = new string[m];
	for (int i = 0; i < m; i++)
		cin >> queries[i];

	Trie trie;
	for (int i = 0; i < n; i++)
		trie.insert(words[i]);

	for (int i = 0; i < m; i++)
		cout << trie.getStat(queries[i]) << endl;

	delete[] words, queries;

	return 0;
}

Author：Who Watson

Link：https://wangshenghu.github.io/2016/05/11/2016-05-11-hihocoder-trie/

Publish date：May 11th 2016, 6:05:08 pm

Update date：December 4th 2022, 5:05:05 pm

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目
  2. 2. 解题思路
  3. 3. 时间复杂度
  4. 4. 代码
Total : 56
2022
2016
test
笔记 算法 hihoCoder 实习经历 项目