踹(Trie)树

· · 个人记录

和 KMP 同理，我一年之前学的快忘光了，赶快写个备忘录。

Trie 树，指字典树，适用于插入一堆字符串并查找他们是否出现过。它的单次插入查询时间复杂度为 O(L)，总共时间复杂度为 O(nL)。空间复杂度上限为 O(nk)，其中 k 为字符串中不同字符的数量。

算法实现

字典树怎么实现查询和插入呢？其实它维护的是一颗树，树上的边表示不同的字母，那么一条从根出发的路径就可以表示一个字符串。

借 OI-wiki 上的一张图：

比如，我们查询 caa 这个字符串，就从根出发，第一次走 c 的边从根节点到达 4 号节点，第二次走 a 的边从 4 号节点到达 8 号节点，第三次走 a 的边从 8 号节点到 12 号节点。那么，4-8-12 这个路径就表示着 caa 这个字符串。

怎么维护这棵树呢？我们发现，对于一个节点，它最多有 k 个儿子（k 为字符串中不同字符的数量）。所以，我们让 tr[p][j] 表示 p 节点下面的表示 k 字符的边连向的节点编号。为了方便存储我们一般把第二位进行压缩处理，比如对于 a 到 z 这些字符我们给他们都减掉 'a'-1，让 a 变成 1，b 变成 2，以此类推。

举个例子，上面的图里面，tr[4][1]（1 表示的是 a）就等于 8，因为 4 号节点下面表示 a 的那个边连向节点 8。

那么这个有什么用呢？其实有很大用处。对于插入一个字符串，我们很容易想到如果这个字符串前几位能够在字典树中找到，那就直接匹配；否则我们就新建一个 tr[p][x] 表示这个节点。

如果我们需要记录哪些字符串被插入了，我们直接在这个字符串结尾对应的点 p 上进行记录。

void insert(char *s,int len,int id)
{
    int p=1; //当前节点，从根节点开始所以 p=1。
    for(int i=0;i<len;i++) // 遍历字符串
    {
        int ch=s[i]-'a'+1;
        if(!tr[p][ch]) tr[p][ch]=++tot; // 如果不存在当前节点那么就插入
        p=tr[p][ch]; // 向下走
    }
    h[p]=id; // 把字符串对应的最后一个节点记录上 id，因为这个点到根节点有且只有一条简单路径所以字符串唯一。
}

对于查询同理，我们就每次向下找，如果没有进行添加节点，字符串就找完了，说明字符串太逊了找到了，否则没找到。

int query(char *s,int len)
{
    int p=1; // 和上面同理，从根节点开始
    for(int i=0;i<len;i++)
    {
        int ch=s[i]-'a'+1;
        if(!tr[p][ch]) return 0; // 有一位匹配不上，说明不存在
        p=tr[p][ch];
    }
    return h[p]; // 能进行到这里说明所有字符都匹配上了，找到了
}

于是这个 Trie 的模板就写完了。其实 Trie 没啥用，真正有用的应该是 AC自动机，而 Trie 是它的重要组成部分。（另一部分是 KMP）

其他の \textrm{trick}