Trie 字典树 Trie
Trie（字典树）是一种用于实现字符串快速检索的多叉树结构。Tire的每个节点都有若干个字符指针，若再插入和检索字符串时扫描到一个字符，就沿字符走向指向的节点。
插入
当需要插入一个字符串时，我们从根走起，依次扫描每一个字符：
- 若字符指向一个已经存在的节点，则顺着节点继续走下去
- 若字符指向空，则新建一个节点，继续走下去。
当字符串中的字符都检索完毕时，记录下其终点结点。
检索
当需要检索一个字符串是否存在时，我们从根走起，一次扫描每一个字符：
- 若字符指向空，则说明不存在，结束。
- 若字符指向一个结点，则继续走下去。
当字符串中所有字符被检索完毕时，若当前结点是一个被标记为终点的节点，说明字符串存在，否则说明其不存在。
1 int trie[SIZE][26], tot = 1; 2 void insert(char* str){ 3 int len = strlen(str), p = 1; 4 for (int k = 0; k < len; k++){ 5 int ch = str[k] - 'a'; 6 if (trie[p][ch] == 0) trie[p][ch] = ++tot; 7 p = trie[p][ch]; 8 } 9 end[p] = true; 10 } 11 bool search(char* str){ 12 int len = strlen(str), p = 1; 13 for (int k = 0; k <= len; k++){ 14 p = trie[p][str[k] - 'a']; 15 if (p == 0) return false; 16 } 17 return end[p]; 18 }