Trie树

基本介绍

Trie树，又称单词查找树，字典树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

Trie树的基本性质可以归纳为：
（1）根节点不包含字符，除根节点意外每个节点只包含一个字符。
（2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
（3）每个节点的所有子节点包含的字符串不相同。
Trie树有一些特性：
1）根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3）每个节点的所有子节点包含的字符都不相同。
4）如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。
5）插入查找的复杂度为O(n)，n为字符串长度。

实现方式

首先，我们以ACA，ACB，AD，CEMD，CEMA五个字符串为例。

很显然，我们构建出来的Trie树就是这个样子。

1、建树

这边我使用的是数组的形式建树，其实用链表也是可以的。

我们以0为根节点，这个节点是不存放任何东西的。

我们从根节点开始，按照需要插入的字符串，一位一位的去判断是否指向该位。

当一个字符串到了结尾的时候，我们可以使用一个flag数组，来表明他是一个字符串的结尾。

int trie[N][26],flag[N],tot;\\tot表示总结点数

void insert(string s) {
	int now = 0, l = s.length();
	for (int i = 0; i < l; i++) {
		int id = s[i] - 'a';
		if (!trie[now][id])	trie[now][id] = ++tot;
		now = trie[now][id];
	}
	flag[now] = 1;
}

2、查询

我们可以从根节点开始查找，按s来一位一位判断，判断该节点是否存在指向这一位的节点的指针。

如果存在，就继续查找。

如果不存在，就直接返回0。

当你查找完成之后，如果最后一位的$flag=1$，说明存在，否则不存在。

int search(string s) {
	int now = 0, l = s.length();
	for (int i = 0; i < l; i++) {
		int id = s[i] - 'a';
		if (!trie[now][id])	return 0;
		now = trie[now][id];
	}
	return flag[now];
}

典型例题

1、HDU 1251 统计难题

题目大意

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

解题思路

因为题目需要求的是以某个单词为前缀的数量，那么我们只需要统计每一位的数量即可。

完整代码

#include <iostream>
#include <string>
using namespace std;

const int N = 1e6 + 5;
int trie[N][30], cnt[N],tot;

void insert(string s) {
	int now = 0, l = s.length();
	for (int i = 0; i < l; i++) {
		int id = s[i] - 'a';
		if (!trie[now][id])	trie[now][id] = ++tot;
		cnt[now]++;
		now = trie[now][id];
	}
	cnt[now]++;
}

int search(string s) {
	int now = 0, l = s.length();
	for (int i = 0; i < l; i++) {
		int id = s[i] - 'a';
		if (!trie[now][id])	return 0;
		now = trie[now][id];
	}
	return cnt[now];
}

int main() {
	string s;
	while (getline(cin, s) && s.length() != 0) {
		insert(s);
	}
	while (cin >> s) {
		cout << search(s) << endl;
	}
}

2、HDU 1075 What Are You Talking About

题目大意

输入几对单词，每对单词存在着对应关系，之后输入一些句子，你需要将其中的单词进行翻译，如果不存在对应关系，则不需要翻译，标点符号不需要翻译。

解题思路

很明显的Trie树模板，只需要将每个单词的结尾记录一下对应的单词即可。

完整代码

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

const int N = 1e6 + 5;
int trie[N][30], tot,flag[N];
string ch[N];

void insert(string s1,string s2) {
	int now = 0, l = s1.length();
	for (int i = 0; i < l; i++) {
		int id = s1[i] - 'a';
		if (!trie[now][id])	trie[now][id] = ++tot;
		now = trie[now][id];
	}
	flag[now] = 1;
	ch[now] = s2;
}

void search(string s) {
	int now = 0, l = s.length();
	for (int i = 0; i < l; i++) {
		int id = s[i] - 'a';
		if (!trie[now][id]) {
			cout << s;
			return;
		}
		now = trie[now][id];
	}
	if (flag[now])	cout << ch[now];
	else cout << s;
}

int main() {
	string s1, s2;
	cin >> s1;
	while (cin>>s1&&s1!="END") {
		cin >> s2;
		insert(s2, s1);
	}
	cin.get();//吸收回车
	while (getline(cin,s1)&&s1!="END") {
		int l = s1.length();
		if (s1 == "START")	continue;
		string s;
		for (int i = 0; i < l; i++) {
			if (s1[i] >= 'a' && s1[i] <= 'z')	s += s1[i];
			else {
				search(s);
				cout << s1[i];
				s.clear();
			}
		}
		cout << endl;
	}
}