有一个常见的字符串匹配问题：在n个字符串中，查找某个字符串。如果用暴力法，需要逐个匹配每个字符串，复杂度为O(nm)，m为字符串的平均长度，效率十分低下。有没有很快的方法？大家都有查英语字典的经验，如查找单词dog，先翻到字典的d部分，再翻到第2个字母o、第3个字母g，一共查找3次即可。查找任意单词，查找次数最多只需要这个单词的长度，与单词的总数量无关。

字典树(TrieTrie，又译为前缀树)就是模拟这个操作的数据结构。字典树是一棵多叉树，如英文字母的字典树是26叉树，数字的字典树是10叉树。字典树是很多其他算法和数据结构的基础，如本章的回文树、AC自动机、后缀自动机，都建立在字典树上。

01、字典树的构造

图1所示为单词be、bee、may、man、mom、he的字典树。多个单词存储时共用相同的前缀(Prefix)。为区分一条链上的不同字符，可以在节点上设置一个标志，标记该节点是否是一个单词的末尾，如图1中的带下画线的阴影字符。这棵字典树用12个节点存储了7个单词，共16个字符。

■ 图1 字典树

从图1可以归纳出字典树的基本性质：①根节点不包含字符，除根节点外的每个子节点都包含一个字符；②从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串；③一个完整的单词并不是存储在某个节点上，而是存储在一条链上；④一个节点的所有子节点都有相同的前缀。

字典树的节点的数据结构可以这样定义：

struct TrieNode {
 <Type> data;
bool isEndOfWord;                   //标记是否为单词的末尾
 TrieNode *children[SIZE];           //指向多个子结点。可能有很多空指针
}

字典树的时间复杂度很好，但空间复杂度比较差。

(1) 时间复杂度。插入和查找一个单词的复杂度为O(m)，其中m为待插入/查询的字符串长度，与整棵树的大小无关。由于一般情况下m很小，可以认为复杂度为O(1)。

(2) 空间复杂度。从表面看，由于多个字符串可以共享相同的前缀，很节省空间。但是在前面所定义的字典树的数据结构中，每个节点都需要设置SIZE个子节点，而其中大多数并不会被用到，导致空间浪费。在后面的例题中，使用了静态数组存储字典树，浪费的空间更多。

提示/

字典树是一种空间换时间的数据结构，所有基于字典树的数据结构和算法都有这个特征。

字典树有以下常见的应用。

(1) 字符串检索。检索、查询功能是字典树的基本功能。

(2) 词频统计。统计一个单词出现次数。

(3) 字典序排序。插入时，在树的平级按字母表的顺序插入。字典树建好后，用先序遍历，就得到了字典序的排序。

(4) 前缀匹配。字典树是按公共前缀来建树的，很适合搜索提示符。例如Linux的行命令，输入一个命令的前面几个字母，系统会自动补全命令后面的字符。字典树常用于处理有相同前缀的字符串问题。

02、模板代码

用下面的例题给出字典树的代码。
例2于是错误的点名开始了(洛谷 P2580)

问题描述： 给出学生人数和名单，教练点名。

输入： 第1行输入一个整数n，表示人数；接下来n行中，每行输入一个字符串表示学生名字(互不相同，且只含小写字母，长度不超过50)；第n+2行输入一个整数m，表示点名的人数；接下来m行中，每行输入一个字符串，表示点名的名字(只含小写字母，且长度不超过50)。

输出： 对于每个教练报的名字，输出一行。如果该名字正确且是第1次出现，输出OK；如果该名字错误，输出WRONG；如果该名字正确但不是第1次出现，输出REPEAT。

求解本题有两种方法：STL map、字典树。

作为参考，首先看本题的STL map代码实现。map做一次插入和查询的复杂度为O(logn)，比字典树慢一些。

提示/

普通的字符串插入和查询，用map处理非常简便，竞赛中如果能用map就用它。

//洛谷 P2580的map实现
#include <bits/stdc++.h>
using namespace std;
int main(){
    map<string,int>student;    string name;
    int n;  cin>>n;
    while(n--){ cin>>name;  student[name]=1; }  //直接把名字当成下标处理
    int m;  cin>>m;
    while(m--){
        cin>>name;
        if(student[name]==1){      puts("OK"); student[name]=2;}
        else if(student[name]==2)  puts("REPEAT");
        else                       puts("WRONG");
    }
    return 0;
}

下面说明如何用字典树解这一题。后面的代码用静态数组存储字典树，而不是用动态分配空间存储字典树。用静态数组在一般情况下会导致很多空间空闲，不过如果存储大量字符串，这些空间都会填满，从整体上看比动态分配更紧凑，更节省空间。

用结构体数组t［］存储字典树的节点。每个节点有26个子节点，即26个小写字母。在一个节点上，若t［now］.son［v-“a”］ !=0，表示这个节点存储了一个字符v，并且让now指向下一个字符的存储位置，now是用cnt累加的一个存储位置。特别地，用t［0］表示字符串的起点，即第1个字符。存储结构如图2所示。

■ 图 2 用静态数组t［］存储字典树

字典树有插入和查询两个主要操作。

(1) 插入操作。例如，存储字符串“ab”，插入第1个字符“a”，设此时cnt=5，令t［0］.son［‘a’-‘a’］=now=cnt=5，表示存储了字符‘a’，且下一个字符存储在t［5］，然后把‘b’存储在t［5］.son［‘b’-‘a’］。若再存储一个字符串“ac”，先查询到‘a’已经存储，且下一个字符存储在now=5位置，那么把字符‘c’存储在t［5］.son［‘c’-‘a’］。

(2) 查询操作。例如,查询字符串“abc”是否存在，先检查t［0］.son［‘a’-‘a’］=now 是否等于0，若now≠0，说明‘a’存在，然后再检查下一个字符‘b’，即查询t［p］.son［‘b’-‘a’］是否等于0，以此类推。

#include <bits/stdc++.h>
using namespace std;
const int N = 800000;
struct node{
    bool repeat;    //这个前缀是否重复
    int son[26];    //26个字母
    int num;        //这个前缀出现的次数
}t[N];              //trie
int cnt = 1;        //当前新分配的存储位置。把cnt=0留给根结点
void Insert(char *s){
    int now = 0;
    for(int i=0;s[i];i++){
        int ch=s[i]-'a';
        if(t[now].son[ch]==0)          //如果这个字符还没有存过
            t[now].son[ch] = cnt++;    //把cnt位置分配给这个字符
        now = t[now].son[ch];          //沿着字典树往下走
        t[now].num++;                  //统计这个前缀出现过多少次
    }
}
int Find(char *s){
    int now = 0;
    for(int i=0;s[i];i++){
        int ch = s[i]-'a';
        if(t[now].son[ch]==0) return 3; //第一个字符就找不到
        now = t[now].son[ch];
    }
    if(t[now].num == 0) return 3;       //这个前缀没有出现过
    if(t[now].repeat == false){         //第一次被点名
        t[now].repeat = true;
        return 1;
    }
    return 2;
 // return t[p].num;                    //若有需要，返回以s为前缀的单词的数量
}
int main(){
    char s[51];
    int n;cin>>n;
    while(n--){ scanf("%s",s); Insert(s); }
    int m; scanf("%d",&m);
    while(m--) {
        scanf("%s",s);
        int r = Find(s);
        if(r == 1)   puts("OK");
        if(r == 2)   puts("REPEAT");
        if(r == 3)   puts("WRONG");
    }
    return 0;
}

示/

字典树是一种基础方法，请掌握字典树的静态数组存储方法，它在后缀树、回文树、AC自动机、后缀自动机中都要用到。