1. 简介

字典树（Trie）用边来代表字母，从根结点到树上某一结点的路径就代表了一个字符串。

2. 实现

• 由于字典树中的字符串都是从根结点开始，于是我们可以通过标记字符串的终止结点来记录已经插入字典树中的字符串。
• 我们用 $\delta(u,c)$ 表示结点 $u$ 的 $c$ 字符指向的下一结点，即在结点 $u$ 代表的字符串后面添加一个字符 $c$ 形成的字符串的结点。
• 由于字典树的分支取决于字符串中最大可能出现的不同字符数 $m$，因此字典树是一棵 $m$ 叉树，我们可以采用动态开点的方式构建字典树。

3. 模板

#include <bits/stdc++.h>
using namespace std;

#ifndef _TRIE_
#define _TRIE_
#define ll int
#define MAXN 100005
#define MAXCHAR 128

//字典树
struct Trie {
    ll cnt;                     // 动态开点（开 Trie 树结点编号）
    ll next[MAXN][MAXCHAR];     // 记录关联边为对应字符的子结点的下表
    bool exist[MAXN];           // 记录以该结点结尾的字符串是否存在
    Trie(): cnt(0) {}
    // 插入字符串
    void insert(char *str, ll len) {
        ll p = 0;
        for(ll i = 0; i < len; ++i) {
            ll c = str[i];
            if(!next[p][c]) {
                next[p][c] = ++cnt;
            }
            p = next[p][c];
        }
        exist[p] = 1;
    }
    // 查找字符串
    bool find(char *str, ll len) {
        ll p = 0;
        for(ll i = 0; i < len; ++i) {
            ll c = str[i];
            if(!next[p][c]) {
                return false;
            }
            p = next[p][c];
        }
        return exist[p];
    }
};
#endif