Trie树
Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树 或 键树，是一种多叉树结构。如下图：
上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质：
- 根节点不包括字符，除根节点之外的每一个结点都包括一个字符。
- 从根结点到达某一个结点，把路径上的字符依次连接起来，就是一个关键字，即代表这个结点的字符串。
- 每个结点的所有子结点都各不相同。
但是，只给出一棵树，没办法知道到达哪一个结点才形成关键字，所以我们通常给出一个变量储存该结点是否为关键字的信息。
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++;
}
}