Trie树

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树 或 键树，是一种多叉树结构。如下图：

上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质：

1. 根节点不包括字符，除根节点之外的每一个结点都包括一个字符。
2. 从根结点到达某一个结点，把路径上的字符依次连接起来，就是一个关键字，即代表这个结点的字符串。
3. 每个结点的所有子结点都各不相同。

但是，只给出一棵树，没办法知道到达哪一个结点才形成关键字，所以我们通常给出一个变量储存该结点是否为关键字的信息。

Trie树一般存储的关键字是字符串，并且Trie树把每个字符串分成一个个字符存储起来，这样，如果有一个字符串u是v的前缀，那么它们是有一条公共路径的，所以Trie又被称作前缀树。

Trie是时空复杂度较优秀的前缀算法，他能在O(n)的复杂度下存储串或者查询串。相比较strstr(查询某字符是n个字符中几个字符串的前缀，复杂度为O(n^2))，能更快速的解决问题，因为Trie将所有的串都集中在了一个树上，不需要用for循环遍历所有串。

Trie结构体:

struct trie_node {
    int cnt; // 标记改结点是否为关键字（有多少个），可以灵活运用，如上述问题应该是拥有这个结点串前缀的字符串数量
    trie_node* trie_child[26]; // 存储各个结点的子结点，假设为a-z，NULL表示不存在该子结点
}；

Trie树的应用：

查询/检索是Trie树最基本的功能，分为两种情况：

• 沿路比较每个字符，如果没有对应的子结点，则该串不存在。
• 如果比较完成且该结点的的标志位不为0，则此串存在。

而插入字符串只需要沿路走，没有结点直接创建即可。

trie_node* creat_trie_node () { // 创建一个trie树结点
    trie_node* node = new trie_node;
    node -> cnt = 0;
   	for (int i = 0; i < 26; i++) node -> trie_child[i] = NULL;
    return node;
}

trie_node* root = creat_trie(); // 定义根节点（在创建函数创建）

int trie_search (char key[]) { // 若串不存在，则返回0，否则返回该串的出现次数
    trie_node* node = root;
    while (*key) { // 查询key的每一个字符
        int id = *key - 'a';
        if (node -> trie_child[id] == NULL) return 0;
        node = node -> trie_child[id];
        key++;
    }
    return node -> cnt;
}

void trie_insert (char key[]) {
    trie_node* node = root;
    while (*key) {
        int id = *key - 'a';
        if (node -> trie_child[id] == NULL) {
            node -> trie_child[id] = creat_trie_node();
        }
        node = node -> trie_child[id];
        key++;
    }
    node -> cnt++;
}

如果测试数据比较多，好需要在测试完一组后进行销毁树的操作，用递归销毁，先销毁子树，再销毁自己。

void destroy_trie (trie_node* root) {
    for (int i = 0; i < 26; i++) {
        if (root -> child[i] != NULL) destroy_trie(root -> child[i]);
    }
    delete root;
}

用数组来模拟Trie树(更快)

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]储存树种每个节点的子结点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert (char* s) {
    int p = 0;
    while (*s) {
        int u = *s - 'a';
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
        s++;
    }
    cnt[p]++;
}

// 查询字符串出现的次数
int query (char* s) {
    int p = 0;
    while (*s) {
        int u = *s - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
        s++;
    }
    return cnt[p];
}

例题

Hat’s Words

如果一个字符串由其他两个字符串拼接而成，则称此字符串为Hat's Words，给出n个字符串，问其中有几个字符串为Hat's Words。

题解：根据n个字符串构造Trie树，然后对每个字符串进行查询，如果查询到一个关键字，则对字符串剩下部分check，如果正好是一个关键字，则为Hat's Words。

bool check (char s[]) {
	trie_node* node = root;
	while (*s) {
		int id = *s - 'a';
		if (!node -> child[id]) return false;
		node = node -> child[id];
		s++;
	}
	return node -> is_key;
}

bool solve (char s[]) {
	char *t = s;
	trie_node* node = root;
	while (*s) {
		int id = *s - 'a';
		if (node -> child[id] != NULL) {
			if (node -> child[id] -> is_key && *(s+1)) {
				if (check(s+1)) return true;
			}
		}
		else break;
		node = node -> child[id];
		s++;
	}
	return false;
}

Repository

给出n个字符串，再给出m次查询，问查询的字符串是多少个给定字符串的子串。

子串可以为任意位置，所以要把给定字符串的每个子集都加入到Trie树中。

题解：Trie高级运用，需要对给定字符串每个后缀插入到Trie树中，插入树时，要记录后缀的每个前缀的出现次数 --> 这样就可以把每个子集加入到Trie中，对于add，插入dd时，root->d加一，但插入d时，root->d又加一，会使d的查询结果加一(add是d的一个超集，但d加了两次)，还需要设置一个f标志表示对于这个字符串而言，某个字符是否前面已经加过，如果加过就不再加。

struct trie {
	int f;
	int cnt;
	trie* child[26];
};

trie* creat_node () {
	trie* node = new trie;
	node -> cnt = 0;
	node -> f = -1;
    for (int i = 0; i < 26; i++) node -> child[i] = NULL;
	return node;
}

void trie_insert (char *s, int f) { // f为给定字符串的顺序，十分巧妙
	trie* node = root;
	while (*s) {
		int id = *s - 'a';
		if (node -> child[id] == NULL) node -> child[id] = creat_node();
		node = node -> child[id];
		if (node -> f != f) { // 说明f序号的给定字符串对于这个子集没有赋值过！
			node -> cnt++;
			node -> f = f; // 把f值赋为f，对于这个字符串，子集就不会重复加入，下一个字符串f+1，又不一样了
		}
		s++;
	}
}