字典树（前缀树）

具体来说，Trie一般支持两个操作：

1. insert(S)：插入操作，就是将一个字符串 S 加入到集合中。
2. search(S)：查询操作，就是查询一个字符串 S 是不是在集合中。

int trie[maxn][26], tot;  // 字典树 & 前缀树
int exist[maxn];  // 有多少字符串在此处结束
int num[maxn];    // 统计前缀个数

void insert(char s[]) { // 插入字典树
    int pos = 0, n = strlen(s+1);
    for(int i = 1; i <= n; ++ i) {
        int j = s[i] - 'a';
        if (trie[pos][j] == 0) {
            trie[pos][j] = ++tot;
        }
        pos = trie[pos][j];
        num[pos] ++;   // 统计前缀个数
    }
    exist[pos] ++; // 标记终点
}

int search(char s[]) { // 查询相同前缀个数
    int pos = 0, n = strlen(s+1);
    for(int i = 1; i <= n; ++ i) {
        int j = s[i] - 'a';
        pos = trie[pos][j];
        if (pos == 0) return 0; // 匹配失败
    }
    return num[pos];
}