一个常见的字符串匹配问题是：在 $n$ 个字符串中，查找某个字符串。如果使用暴力法，需要逐位匹配每个字符串，复杂度为 $O(nm)$，其中 $m$ 为字符串的平均长度，这样的效率显然太低。
借用现实生活的经验，我们其实无需按照这 $n$ 个字符串的顺序一个一个看下来，而是先找到第一个字母，再看第二个字母……查找任意一个单词，查找次数都只要这个单词的长度，而和单词的总数量无关。
这就是 字典树（Trie，Retrieval Tree 的缩写），又译为前缀树，它模拟了这个过程，就像是翻阅字典一样。字典树是一种多叉树，如英文字母的字典树是 $26$ 叉树，数字的字典树是 $10$ 叉树。
字典树是其他很多算法和数据结构的基础。
字典树的构造
特征
以只含小写字母的字符串为例，对于具有相同前缀的单词，它们的每一位父节点都是一样的：也就是说， 多个单词存储时共用相同的前缀（Prefix）。为了区分同一条链上的不同字符，可以在节点上设置一个标志，标记这个节点是否是一个单词的末尾。
性质
- 根节点不包含字符，除根节点之外的每一个节点都包含一个字符。
- 从根节点到某个节点，路径上所经过的字符连接起来，就是这个节点对应的字符串。
- 一个完整的单词并不是存储在某个节点上，而是存储在一条链上。
- 一个节点的所有子节点都具有相同的前缀。
定义数据结构
struct TrieNode
{
<Type> data;
bool is_end_of_word; // 标记是否是单词的末尾
TrieNode * children[SIZE]; // 指向多个子节点
};复杂度分析
字典树具有较好的时间复杂度：插入和查找一个单词的复杂度都是 $O(m)$，其中 $m$ 为待插入/查询的字符串长度，与整棵树的大小无关。
但就像线段树一样，它的空间复杂度较差：每个节点都需要设置 SIZE 个子节点，而大多数并不会被用到。而常用的更容易编码的静态数组存储将会浪费更多的空间。
像 BFS 一样，字典树是一种 空间换时间 的数据结构。所有基于字典树的数据结构和算法都具有相似的特征。
应用
- 字符串检索
- 词频统计
- 字典序排序：插入时，在树的平级按字母表的顺序插入。字典序建好之后，再利用先序遍历，就得到了字典序的排序。
- 前缀匹配：对于相同的前缀筛选单词
模板代码
字典树模板题：P2580 于是他错误的点名开始了
观察题目，发现这是一道普通的字符串匹配问题，有两种解决方式：STL map 和 字典树。
STL map
STL map 进行插入和查询的复杂度为 $O(\log_2 n)$，比字典树慢一些。
#include <iostream>
#include <map>
using namespace std;
int read()
{
int x = 0, f = 1;
char ch = 0;
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int n, m;
string name;
map<string, int> student;
int main()
{
n = read();
while (n--)
{
cin >> name;
student[name] = 1;
}
m = read();
while (m--)
{
cin >> name;
if (student[name] == 1)
{
printf("OK\n");
student[name] = 2;
}
else if (student[name] == 2)
printf("REPEAT\n");
else
printf("WRONG\n");
}
return 0;
}字典树
STL map 进行插入和查询的复杂度为 $O(\log_2 n)$，比字典树慢一些。
用静态数组存储
首先，用结构体数组 t[] 存储字典树的节点。每个节点都有 $26$ 个子节点，即 $26$ 个小写字母。
在某个节点上，如果 t[now].son[v - 'a] != 0，就表示这个节点存储了一个字符 v，并且让 now 指向下一个字符的存储位置，now 是用 cnt 累加的一个存储位置。特别地，用 t[0] 表示字符串的起点，即第 $1$ 个字符。
操作
字典树有插入和查询两个主要操作
插入操作
假设存储字符串 "ab"。首先插入第一个字符 'a'，假设此时 cnt = 5，那么令 t[0].son['a' - 'a'] = now = cnt = 5，表示存储了字符 'a'，并且下一个字符存储在 t[5]，也就是 'b' 要存储在 t[5].son['b' - 'a']。
如果还需要再加入一个字符串 "ac"，那么首先查询到 'a'已经存储，并且 t[0].son['a' - 'a'] = 5，然后再存储 'c'，即 t[5].son['c' - 'a'] 上。
查询操作
例如，查询字符串 "abc" 是否存在，就先检查 t[0].son['a' - 'a'] = now 是否等于 $0$，如果不为 $0$，就说明 'a' 存在，进一步检查字母 'b'……以此类推。
模板代码
#include <iostream>
#include <cstring>
using namespace std;
int read()
{
int x = 0, f = 1;
char ch = 0;
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
const int maxN = 1e6;
struct node
{
bool repeat; // 这个前缀是否重复
int son[26]; // 26个英文字母作为子节点
int sum; // 前缀出现的次数
bool isEnd; // 是否为单词的结尾
} t[maxN];
int cnt = 1; // 当前新分配的存储位置
int n, m;
char s[55];
void insert(char *s)
{
int now = 0;
for (int i = 0; i < s[i]; i++)
{
int ch = s[i] - 'a';
if (t[now].son[ch] == 0) // 这个字符还没有存储过
t[now].son[ch] = cnt++; // 把当前的位置分配给它
now = t[now].son[ch]; // 沿着字典树向下走
t[now].sum++; // 统计这个前缀出现过多少次
if (i == strlen(s) - 1)
t[now].isEnd = true;
}
}
int find(char *s)
{
int now = 0;
for (int i = 0; i < s[i]; i++)
{
int ch = s[i] - 'a';
if (t[now].son[ch] == 0)
return 3;
now = t[now].son[ch];
}
if (t[now].isEnd == false)
return 3;
if (t[now].sum == 0) // 这个前缀没有出现过
return 3;
if (t[now].repeat == false)
{
t[now].repeat = true;
return 1;
}
return 2;
}
int main()
{
n = read();
while (n--)
{
scanf("%s", s);
insert(s);
}
m = read();
while (m--)
{
scanf("%s", s);
int r = find(s);
if (r == 1)
printf("OK\n");
else if (r == 2)
printf("REPEAT\n");
else
printf("WRONG\n");
}
return 0;
}
