字典树 (单词查找树, Trie, /ˈtraɪ/): 是一种有序树，用于保存关联数组，其中的键通常是字符串。

字典树

时间复杂度：$O(m)$

$m$ 为待操作字符串的长度。

分析

储存多个字符串的朴素方法就是将字符串储存到多个字符数组内，但这样储存比较占用空间，并且查询操作比较费时。

如果字符串的字符种类较少，例如只有小写字母、只有大写字母、只有数字、只有 0/1 这种情况，就可以使用字典树这一种数据结构（也可以使用二进制转化为 0/1 的情况）。

（图片来源：Wikipedia，属于公有领域）

实现方式，与链表比较类似。使用了一个二维数组储存子节点指针，第一维代表节点序号，其中 $0$ 号节点代表头节点，也代表空节点，节点结尾指向空节点。第二维代表字母，若储存小写字母，则需要 $26$ 个，$0\sim25$ 分别代表 $a\sim z$.

代码实现

（以下代码示例储存的为小写字母）

插入

const int MAXN = 1e6 + 10;
int son[MAXN][26], cnt[MAXN], idx;

void insert(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; i++)
    {
        int c = str[i] - 'a';
        if (!son[p][c])
            son[p][c] = ++idx;
        p = son[p][c];
    }
    cnt[p]++;
}

查询

返回待查询字符串的数量。

int query(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; i++)
    {
        int c = str[i] - 'a';
        if (!son[p][c])
            return 0;
        p = son[p][c];
    }
    return cnt[p];
}