Trie 树是一颗像字典一样的树。
在 Trie 树上用边来表示字母，一个节点到另一个节点的边就是一个字母。
实现：
点击查看代码
void insert (char s[]) {
int u = 0, len = strlen (s);
for (int i = 0; i < len; i ++) {
int v = gt (s[i]);
if (!son[u][v]) son[u][v] = ++ cnt;
u = son[u][v];
w[u] ++;//以v为结尾的字符串个数
}
}
int find (char s[]) {
int u = 0, len = strlen (s);
for (int i = 0; i < len; i ++) {
int v = gt (s[i]);
if (!son[u][v]) return 0;
u = son[u][v];
}
return w[u];
}
例题：P2580 于是他错误的点名开始了 基础操作。
P3879 [TJOI2010] 阅读理解 虽然要用bitset卡空间