字典树略解

字典树（$Trie$Trie树），是哈希树的一种，主要用来字符串操作
它充分利用了字符串的公共前缀，从而实现字符串的快速检索

在我们认识字典树之前，我想给大家看一道题：

给你$n$n个单词构成一个词典，现在再给你$m$m个单词，问这$m$m个单词是否存在于字典中。

“这不很简单吗！直接一个$set$set就解决了”

“字符串$hash$hash也可以！”

那好，我们把题目稍稍变难一点：

给你$n$n个单词构成一个字典，现在再给你$m$m个前缀，问字典中有多少个单词有这个前缀。

暴力比对好像不行，但有人会说：

“先对单词进行$hash$hash，再对前缀$hash$hash，一个一个比就行了嘛！”

好的！这只是热身，真正的题目到了！

POJ 2001 Shortest Prefixes

Description

A prefix of a string is a substring starting at the beginning of the given string. The prefixes of “carbon” are: “c”, “ca”, “car”, “carb”, “carbo”, and “carbon”. Note that the empty string is not considered a prefix in this problem, but every non-empty string is considered to be a prefix of itself. In everyday language, we tend to abbreviate words by prefixes. For example, “carbohydrate” is commonly abbreviated by “carb”. In this problem, given a set of words, you will find for each word the shortest prefix that uniquely identifies the word it represents.

In the sample input below, “carbohydrate” can be abbreviated to “carboh”, but it cannot be abbreviated to “carbo” (or anything shorter) because there are other words in the list that begin with “carbo”.

An exact match will override a prefix match. For example, the prefix “car” matches the given word “car” exactly. Therefore, it is understood without ambiguity that “car” is an abbreviation for “car” , not for “carriage” or any of the other words in the list that begins with “car”.

Input

The input contains at least two, but no more than 1000 lines. Each line contains one word consisting of 1 to 20 lower case letters.

Output

The output contains the same number of lines as the input. Each line of the output contains the word from the corresponding line of the input, followed by one blank space, and the shortest prefix that uniquely (without ambiguity) identifies this word.

Sample Input

carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate

Sample Output

carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona

题目大意

现在题目给你$n$n个单词，要求对每一个单词，找到一个最短且能将其与其他单词区分开来的最短的前缀。

比如，caribou和carriage有一个共同前缀carr，这时，能区分这两个单词的最短前缀分别是carib和carri

“我还是选择$hash!$hash!”

但如果我们仔细想想：如果要$hash$hash，必须对于每个单词的每个前缀进行$hash$hash，然后再将这些前缀依次比对，这样算法是$O(\prod|S|)$O(∏∣S∣)的时间复杂度的，超时

这时，字典树闪亮登场！

题目要求的，其实就是公共前缀带上个下一位。

于是，我们可以利用公共前缀，画出这样的树：(假设现在我们有apple,apart,adjust,bike,bit这些单词)
（图丑请忽略 ）

我们可以从图中看到，字典树充分利用了这些单词的公共前缀，形成了如图所示的树形结构。

“等等，为什么根节点是空的？”

如果根节点也带上相应的字母，那么就形成了森林，其中每棵树的根节点就是单词的首字母。显然，森林不是我们想要的，于是我们建立一个虚拟节点，将该节点与森林中每棵树的根节点相连，就形成了真正的字典树，这个虚拟节点就成了虚拟的根节点

那么，如何建立一颗字典树呢?

插入

我们不妨将每一个节点标上号，其中字典树根节点的编号为0。

对于每一个节点，都有他自己的字符指针（当然，这里我们是用数组模拟指针），初始化为空。同时，我们令根节点的指针为$pos$pos

对于字符串$S$S中的每一个字符$c$c：

1.若$pos$pos的$c$c字符指针已经指向节点$tmp$tmp，则令$pos=tmp$pos=tmp

2.否则，新建一个节点$tmp$tmp，让$pos$pos的$c$c字符指针指向$tmp$tmp，再令$pos=tmp$pos=tmp

当$S$S扫描完毕时，在当前节点上标记一下他是一个字符串的结尾（当然，这步可以不做，视具体题目而定）

检索

（变量名含义同上）

对于字符串$S$S中的每一个字符$c$c：

1.若$pos$pos的$c$c字符指正为空，则在$Trie$Trie中没有该字符串，返回假

2.否则，令$pos$pos指向他的字符指针$c$c

当扫描完毕时，如果当前节点有标记，则说明在$Trie$Trie中存在该字符串，如果没有，则说明该字符串是字典树中某字符串的前缀（这点很重要）

字典树的空间复杂度是$O(nc)$O(nc)的，其中$n$n是节点大小，$c$c是字符集的大小。

一般的，我们用数组来写字典树的时候，能开多大就开多大，一般开到字符串长度的总和。

代码

（我们这里采用数组的方式存储字典树，当然，从节省空间的角度来看，指针无疑更好，但指针难写，而且容易出错，初始化不好会造成指针指向空的错误）

1.Trie树的声明

struct Trie{
	int son[26];//字符指针
	int flag;//单词末尾标记
	Trie(){
		memset(son,0,sizeof(son));
		flag=0;
	}
}trie[maxn];

2.插入

inline void insert(char *s){
	int pos=0;//根节点
	int len=strlen(s);
	for(int i=0;i<len;i++){
		int tmp=s[i]-'a';
		if(!trie[pos].son[tmp])//新增节点
			trie[pos].son[tmp]=++tot;
		pos=trie[pos].son[tmp];//迭代
	}
	trie[pos].flag=1;
}

最后献上本题的AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
string s[1005];
int n;
struct Trie{
	int son[50];
	int cnt;
	Trie(){
		memset(son,0,sizeof(son));
		cnt=0;
	}
}trie[20*1005];
int tot;
inline void insert(string str){
	int pos=0;
	for(int i=0;i<str.size();i++){
		int tmp=str[i]-'a'+1;
		if(!trie[pos].son[tmp]) trie[pos].son[tmp]=++tot;
		pos=trie[pos].son[tmp];
		trie[pos].cnt++;
	}
}
inline string query(string str){
	string ans="";
	int pos=0;
	for(int i=0;i<str.size();i++){
		int tmp=str[i]-'a'+1;
		ans.push_back(str[i]);
		pos=trie[pos].son[tmp];
		if(trie[pos].cnt==1) return ans;
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	while(cin>>s[++n]);
	for(int i=1;i<=n;i++) insert(s[i]);
	for(int i=1;i<=n;i++) cout<<s[i]<<' '<<query(s[i])<<endl;
	return 0;
}

之后我会慢慢更新字典树的更多例题的~

文章中如有错误请指正，我会尽快改正。