简介

字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串）。优点是利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

Trie

字典树的结构如下：

trie

字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。这颗字典树包含的字符串有{“in”, “inn”, “int”, “tea”, “ten”, “to”}。

Trie的结构非常好懂，我们用$\delta(u, c)$表示结点u的c字符指向的下一个结点，或着说是结点u代表的字符串后面添加一个字符c形成的字符串的结点。（c的取值范围和字符集大小有关，不一定是0~26）。有时需要标记插入进 trie 的是哪些字符串，每次插入完成时在这个字符串所代表的节点处打上标记即可。

Trie一般支持两个操作：

  1. 插入操作，就是将一个字符串s加入到集合中。
  2. 查询操作，就是查询一个字符串S是不是在集合中。

实现代码如下：

 1void insert(char *s, int n)
 2{
 3    int p = 0;
 4    for (int i=0; i<n; i++)
 5    {
 6        int c = s[i] - 'a';
 7        if (!tree[p][c]) tree[p][c] = ++cnt;
 8        p = tree[p][c];
 9    }
10    exist[p]++;
11}
12
13int search(char *s, int n)
14{
15    int p = 0;
16    for (int i=0; i<n; i++)
17    {
18        int c = s[i] - 'a';
19        if (!tree[p][c]) return 0;
20        p = tree[p][c];
21    }
22    return exist[p];
23}

模板

 1char s[mxn];
 2int tree[100000][26], exist[100000], cnt = 0;
 3
 4void insert(char *s, int n)
 5{
 6    int p = 0;
 7    for (int i=0; i<n; i++)
 8    {
 9        int c = s[i] - 'a';
10        if (!tree[p][c]) tree[p][c] = ++cnt;
11        p = tree[p][c];
12    }
13    exist[p]++;
14}
15
16int search(char *s, int n)
17{
18    int p = 0;
19    for (int i=0; i<n; i++)
20    {
21        int c = s[i] - 'a';
22        if (!tree[p][c]) return 0;
23        p = tree[p][c];
24    }
25    return exist[p];
26}
27
28int main()
29{
30    int n, m; scanf("%d %d", &n, &m);
31    for(int i=0; i<n; i++){
32        scanf("%s", s);
33        insert(s, strlen(s));
34    }
35    for(int i=0; i<m; i++){
36        scanf("%s", s);
37        printf("%d\n", search(s, strlen(s)));
38    }
39    return 0;
40}