字典树 / trie树

定义

当我手里有若干个字符串的时候，现在向你询问某个字符串时候是前面的这些字符串中的其中之一。如果我们用暴力的做法来求解的话，我可能需要对这些字符串进行逐一比对，效率是相当低的。那么这个时候我们就可以用 trie 树的结构简单高效的解决这个问题。

这个结构实现的原理有点像主席树（跑题了），字典树的根节点是一个空间点，没有任何含义，仅仅表示这棵字典树遍历的一个起点。

然后从根节点开始，构建我们的字典树，例如：把 “abcd”, “acd”, “bcd”, “abce” 这四个字符串构建成一棵字典树。那么这棵树就会长成下面的样子：
字典树1
我们从根节点出发，走到任意一个节点，走过的路径都是一个字符串。例如：空 -> a -> c -> d 就表示字符串 “acd”。

代码实现

首先先来说一下构建字典树的代码，根据个人的习惯和应用的环境，其实写法还是五花八门的，这里只是引出一种供大家参考。

int trie[maxn][30], tot = 1, cnt[maxn];
string s;void creat_trie(int id)
{int u = 1, len = s.size(); // u 表示当前在树上的位置for (int i = 0; i < len; i++) // 从前往后枚举每一个字符，这个被枚举出来的字符就是我们要在 u 下面添加的字符{int v = s[i] - 'a' + 1; // 用数字代替if (!trie[u][v]) // 如果还没被添加就添加trie[u][v] = ++tot; u = trie[u][v]; // 如果已经被添加了就顺着走}cnt[u]++; // 从根节点走到 u 表示的字符串是一个我们想要维护的字符串
}

首先我们让根节点的编号为 1，然后依次构建每一个字符串，也就是把一个字符串添加进字典树之后，再考虑下一个字符串。我们从根节点走到节点 u，路径上所有的点构成一个字符串（有可能是空串），那么在这个字符串后面如果再加上一个字符的话，我们假设这个字符是 ‘a’，那么我们就用一个节点来表示，如果这个点已经存在了，我们就不用管，直接移动到这个点就好，否则就新建一个点，给它一个编号，并让 trie[u][1] 等于这个新的点的编号，以此维护字典树的结构。

然后我们再来看如何查询一个字符串是否在这个字典树上。

int trie[maxn][30], tot = 1, cnt[maxn];
string s;bool check(string x)
{int u = 1;for (int i = 0; i < x.size(); i++){int a = x[i] - 'a' + 1;if (!trie[u][a]) // 看看下一个字符在不在树上return false;u = trie[u][a];}if (cnt[u])return true;return false;
}