Trie树（字典树）

编程 数据结构

Description
小明有很多单词(全部由小写字母组成，不会有重复单词)，现在他想统计以某个字符串为前缀的单词数量(单词本身也是自己的前缀)。

Input
输入n,然后n行每行一个单词，长度不超过10,这n个单词构成字典库
接下来m,然后m行每行一个单词前缀(1<=n<=100000,1<=m<=50000)
Output
对于每个单词前缀，问字典库中以它为前缀的单词有多少个

一些简单的算法

首先，这道题暴力枚举的时间复杂度是O(nm*len),很明显回超时。那么怎么办呢？
观察样例，发现排序后，具有相同前缀的单词会在一起，并且，排序后的序列具有单调性，使我们可以通过二分答案法来解决这道题，具体步骤如下：

1. 输入字符串，快速排序 （时间复杂度 O(nlgn*len) )。
2. 二分查找每一个前缀的在序列中第一个出现的单词的位置，即为loc1 （时间复杂度 O(m*lgn*len) ）。
3. 二分查找每一个前缀的在序列中最后一个出现的单词的位置，即为loc2 ( 时间复杂度同 2. )。
4. loc2-loc1+1即为所求的答案。注意判断不存在的情况，可以通过特判或初值定不同来区分。

Trie树（字典树）

引入

算法的名字很好地概括了算法的核心思想，那么什么是字典树的？
大家都知道字典中的单词是按字典序排列的，现在假设有4个单词 a，ab，abc，abd
如果用普通的char类型来存储，一共需要9个char，但是，我们觉得有点浪费，浪费在哪呢？
a
ab
abc
abd
我们发现这四个单词的第一个字母都是a，对于后面3个单词，它们都有ab的前缀。如果用一棵树来存储这些单词，会不会省空间呢？

思想及时间复杂度分析

如图：

如果用一个26叉树来存储上述的单词，我们只需要5个节点就可以了，
更棒的是，随着单词数量的增加，单词之间的前缀重复也会越来越多，能够节省的空间也会越来越多。

我们现在来分析一下其的时间复杂度，假设有n个单词，平均长度为len。对于每个单词，都会访问（创建）len个节点，所以时间复杂度可以认为是O（n*len）

代码( Only Pascal )

只有 Pascal，C++的同学可以使用Map头文件Easiest地解决。

root:=1; nodenum:=1; //初始化 root表示树的根 nodenum表示节点数量
readln(s);
len:=length(s); //s的长度
ins(root,1); 
procedure ins(root:longint; s:string);  //trie的非递归版本插入
var
    now,son,i:longint;
begin
    now:=root;
    for i:=1 to length(s) do
    begin
        son:=ord(s[i])-96;
        if trie[now,son]=0 then
        begin
            inc(nodenum);
            trie[now,son]:=nodenum;
            trie[nodenum,27]:=1;
        end
        else inc( trie[ trie[now,son] ,27] );
        now:=trie[now,son];
    end;
end;
function find_trie(root:longint; s:string):longint;  //trie的非递归版本查找
var
    now,i,son:longint;
begin
    now:=root;
    for i:=1 to length(s) do 
    begin
        son:=ord(s[i])-96;
        if trie[now,son]=0 then exit(0);
        now:=trie[now,son];
    end;
    exit(trie[now,27]);
end;
procedure ins(u,loc:longint); // trie树的递归版本插入
var son:longint;
begin
    if loc>len then exit;
    son:=ord(s[loc])-96;
    if trie[u,son]=0 then 
    begin //新建节点
        inc(nodenum); 
        trie[u,son]:=nodenum; 
        inc(trie[nodenum,27]);
    end
    else inc(trie[ trie[u,son] ,27]);
    ins(trie[u,son],loc+1);
end;

相关题目

最大XOR路径 | 解题报告