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 }
原文：https://www.cnblogs.com/hnoi/p/11361040.html