字典树的定义

又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

(百度百科)

字典树的性质

  • 根节点不包含字符,除根节点外每一个节点都只包含一个字符
  • 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串
  • 每个节点的所有子节点包含的字符都不相同

字典树的用途

  1. 字符串排序

    按照字典序排序字符串.只需要构建一棵字典树,并且令它的儿子们按照字母的字典序从左到右排列,然后对字典树先序遍历即可

  2. 最长公共前缀问题

    用所有字符串建立字典树,然后两个串的最长公共前缀只需要找到它们的公共祖先,然后计算深度就可以了.

  3. 字符串的查找

    用给定的串建立字典树,然后用需要匹配的串在字典树上查找.

字典树的建立

我们设$trie[i][j]$表示第i个节点的第j个儿子的节点编号.采用动态开点.下面的伪代码表示插入一个字符串的过程

inline void insrt(char a[]) {
    l = length(a), 当前节点 = 0;
    for i = 0 to l
        if 当前节点没有第a[i]个位置的儿子 then
            新建节点;
            当前节点 = 新节点;//模拟递归
        else 
            当前节点 = 第a[i]个位置的儿子;
    return;
}

例题:于是他错误的点名开始了

这道题差不多是$trie$字典树的模板题.首先我们可以用题目给出的所有名字建立一个$trie$,然后对于教练报的每一个名字,我们都可以在字典树上一个一个字符地匹配到.对应题目中的三种输出,我们寻找的结果有三种情况:

  • 成功找到了单词的最后一位,返回OK
  • 成功找到了单词的最后一位,但是已经找到过至少一次了,返回REPEAT
  • 没有找到单词的最后一位,返回WRONG

那么我们怎么知道找没找到过呢?由字典树的性质我们可以知道,表示一个单词的树链是唯一确定的,所以我们只需要在链尾节点记录一个被找到的次数,就可以确定返回什么了.代码:

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

int n, m;
char name[10005][51], ask[55];

struct node {
    int to[500005][26], size = 0, times[500005];
    inline void insrt(char a[]) {//插入一个字符串
        int l = strlen(a), now = 0, i;//now表示当前节点
        for (i = 0; i < l; ++i) {//循环模拟递归
            if (!to[now][a[i] - 96]) {//如果没有这个儿子
                to[now][a[i] - 96] = ++size;
                now = size;
            }
            else//有这个二儿子
                now = to[now][a[i] - 96];
        }
        return;
    }
    inline int query(char a[]) {//查询字符串被找到了几次
        int l = strlen(a), now = 0, i;
        for (i = 0; i < l; ++i) {
            if (!to[now][a[i] - 96])//这个单词不在字典树中
                return 0;
            else now = to[now][a[i] - 96];//这个单词在字典树中
        }
        times[now]++;
        return times[now] > 1 ? 2 : 1;
    }
}trie;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        scanf("%s", name[i]);
        trie.insrt(name[i]);
    }
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        scanf("%s", ask);
        int ans = trie.query(ask);
        if (!ans)
            printf("WRONG\n");
        if (ans == 1)
            printf("OK\n");
        if (ans == 2)
            printf("REPEAT\n");
    }
    return 0;
}

字典树的其他应用

给出一个数列$a_1…a_n$,询问这个数列中的最大异或数对,即求$max_{i,j\in [1,n]}(a_i\ xor\ a_j)(i\neq j)$.

这里有很多数,所以我们显然不能直接对数开$trie$.而题目要求我们异或,所以一个自然的想法就是用每个数的二进制建树,这样就可以使得$trie$只有二叉并且深度不会太大,最大$log_2a_i$.接下来我们怎么异或呢?显然的,字典树上的寻找是需要一个基准的.我们对于每一个$a_i$,在字典树上寻找另一个数进行异或.而由异或的定义我们知道,我们寻找的数的每一位是尽量和$a_i$不同的,而且要优先考虑高位.因此我们在字典树上可以直接由高位到低位贪心,在字典树上有这一叉的前提下,如果$a_i$这一位是1,我们就寻找0,否则寻找1,这样最后找到的数和$a_i$异或起来就可以保证最大了.由于代码简单这里就不再出示.

——Gensokyo