博客

正规的字典树的数据结构，使用指针指向下一层子树。但是有写空间要求较高的题目使用指针的方法有可能会MLE。所以使用数组来实现字典树的数据结构是一种更好更紧凑的方法，这种方法更为保险
以hdu 1251为例

题目大意

很多单词只由小写字母组成，不会有重复的单词出现，统计出以某一个字符串为前缀的单词数量。

前半部分读入：

dcba
debf

对于这一部分的读入我们要做到的是建树和统计

int trie[1000010][26];
int num[1000010]={0};
int pos=0;
void Insert(char str[]){
	int p=0;
	for(int i = 0;str[i];i++){
		int n=str[i]-'a';
		if(trie[p][n]==0)
			trie[p][n]=++pos;//独立编号
		p=trie[p][n];
		num[p]++;//统计
	}
}

第一个字符串建树后：

二维数组中每个元素的值，都表示下一跳要去哪一层

第二个字符串建树后：

从第一层跳到第二层中发现第二层中有两个元素值。说明他们有共同的前缀
后一个字符串的下一跳就到第五层了

我们对于没有相同前缀的独立子串，都给它的每一个字符一个单独的编号，方便查找以某一个字符串为前缀的单词数量

另设一个num[ ]数组来存放以当前子串为前缀的单词数量
以本题为例：
num[1]=>以”d”为前缀的单词数量
num[6]=>以”bea”为前缀的单词数量
num[4]=>以”dcba”为前缀的单词数量

第二部分读入：
dcb
当建树和统计都完成后，剩下的就是一个查询的过程了，find( )函数的功能就是查找给出的字符串的每个前缀字串的单词数量

int Find(char str[]){
	int p=0;
	for(int i=0;str[i];i++){
		int n=str[i]-'a';
		if(trie[p][n]==0)
			return 0;
		p=trie[p][n];
	}
	return num[p];
}

以本题为例
Find()函数中的循环
先找了以d为前缀的单词个数=>num[1]
再找以dc为前缀的单词个数=>num[2]
再找以dcb为前缀的单词个数=>num[3]

但凡有等于0的情况，说明没有以当前字符串为前缀的单词，直接退出