字典树

字典树也称Trie树，用树存储和查找字符串。

字典树是一个k叉树，使用k叉树的邻接表存储；

tree[i][j] $\neq$ 0表示结点i有第j个孩子且编号为tree[i][j]，tree[i][j] = 0表示结点i没有第j个孩子，cnt[i]存储以当前结点结尾的字符串个数，d为数组已用位数的下一位；

int tree[n][k], cnt[n], d = 1;

插入字符串str：

void insert(char str[]) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        // 计算str[i]是tree[p]的第t个孩子
        if (!tree[p][t]) tree[p][t] = d++;
        p = tree[p][t];
    }
    cnt[p]++;
}

查找字符串str，返回str的个数：

int search(char str[]) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        // 计算str[i]是tree[p]的第t个孩子
        if (!tree[p][t]) return 0;
        p = tree[p][t];
    }
    return cnt[p];
}

注解：

(1)0号结点是根结点，不存储实际值，其k个孩子表示字符串的k种开头字符。

---