Tire 是一种用于实现字符串快速检索的多叉树结构。Tire的每个节点都拥有若干个字符指针，若在插入或检索字符串时扫描到一个字符c，就沿着当前节点的c字符指针，走向该指针指向的方向。
基本操作：
int trie[SIZE][26], tot = 1; bool End[SIZE]; void insert(char* str) { int len = strlen(str), p = 1; for (int k = 0; k < len; k++) { int ch = str[k] - ‘a‘; if (trie[p][ch] == 0) trie[p][ch] = ++tot; p = trie[p][ch]; } End[p] = true; } bool search(char* str) { int len = strlen(str), p = 1; for (int k = 0; k < len; k++) { p = trie[p][str[k] - ‘a‘]; if (!p) return false; } return true; }
HDU 1251
在树上每个节点存储一个整数cnt，记录该节点是多少个字符串的末尾节点。 对于每个询问，当遍历到最后一个字符时，统计答案。
struct Node { int cnt; int idx; }; Node trie[1000010][26]; int tot = 1; bool End[1000010]; void insert(char* str) { int len = strlen(str), p = 1; for (int k = 0; k < len; k++) { int ch = str[k] - ‘a‘; if (trie[p][ch].idx == 0) trie[p][ch].idx = ++tot; trie[p][ch].cnt++; p = trie[p][ch].idx; } End[p] = true; } int search(char* str) { int sum = 0; int len = strlen(str), p = 1; for (int k = 0; k < len; k++) { if (k == len-1) return trie[p][str[k] - ‘a‘].cnt; p = trie[p][str[k] - ‘a‘].idx; if (p == 0) return 0; } //return End[p]; } char s[105]; int main() { //int f = 0; while (gets(s)) { if (s[0] == ‘\0‘) break; insert(s); } while (~scanf("%s", s)) { int res = search(s); printf("%d\n", res); } }
原文：https://www.cnblogs.com/hznumqf/p/13291999.html