Trie树

Trie（字典树）是一种用于实现字符串检索的多叉树。

Trie的每一个节点都可以通过 c 转移到下一层的一个节点。

我们可以看作可以通过某个字符转移到下一个字符串状态，直到转移到最终态为止。这是后话……

我们以插入了字符串 ab，aa，b 三个字符串的Trie树为例：

其实一看图就非常清晰了

在上图中，如果我们需要继续插入一个字符串 abc，那么就只需要新建一个节点即可

思路清晰，那么代码如何实现？

首先是插入部分：

struct Node {
    int kids[65];
    int cnt;
} nodes[N];

#define kids(p, j) nodes[p].kids[j]
#define cnt(p) nodes[p].cnt

void insert(char * s, int len) {
    int p = 0;
    for (int i = 0; i < len; ++i) {
        int j = discrete(s[i]);
        if (!kids(p, j)) kids(p, j) = ++usage; // 新建节点
        p = kids(p, j);
    }
    ++cnt(p);
}

discrete指的是离散化，例如这里是将 a-z 用 0-25 表示

最终的 cnt 表示有几个字符串在当前节点结束。

然后是查询部分

我们还是利用类似的思路，一个一个向下走。

例如我们要查询字符串 aba，那么我们从根节点 0 开始，通过 a 走到 1 节点，通过 b 走到 4 节点，发现没有 a 的子节点，表明没有这个字串，结束寻找。

// 这里是查询这个字符串出现了多少次，为0就是没有出现
int count(char * s, int len) {
    int p = 0;
    for (int i = 0; i < len; ++i) {
        int j = discrete(s[i]);
        if (!kids(p, j)) return 0;
        p = kids(p, j);
    }
    return cnt(p);
}

其实主要操作就这两个，我们考虑一下空间和时间复杂度：

时间复杂度很明显是与字符串长度相关的，我们每处理一个字符走一个节点，也就是 $O(L)$ 的复杂度，那么总的复杂度就是 $O(NL)$

至于空间复杂度，每处理一个字符串至多新建 $L$ 个节点，那么就是 $O(L)$ ，每一个节点的大小关乎字符串的字符集大小，所以我们认为是 $O(C)$ 那么总共就是 $O(NLC)$ ，但是，在实际中，远远达不到此复杂度（除非毒瘤出题人想卡你），例如最初的图，一共 4 个字符串，但是只有 5 个节点……

例题

【模板】字典树 - 洛谷

注意题意，以询问所给作为前缀，求有多少个字符串满足此前缀
那么我们需要魔改一下 insert 函数即可……将 ++cnt(p) 放入循环中即可
还请读者仔细思考

[USACO12DEC]First! G - 洛谷

这道题非常的神奇……考虑先建Trie树，如果某一个字符串的字典序比其他任何字符串都大，那么一定不存在为其前缀的字符串。
再考虑字典序，如果使 s 其字典序最大，那么每一个分叉点上，s[i] 比其他所有存在的分叉都要大。
如样例：omm, moo, mom。
如果要使 omm 最大那么在第一层上满足 o > m，其他层上没有分叉。
如果要使 moo 最大，那么第一层上满足 m > o，第三层上满足 o > m，条件相悖，所以不可行。
其他同理。
那么我们如何判断条件相悖？可以借鉴 2-SAT 的思路，通过大于关系建图，如果存在环，那么不可行。
判环用拓扑，谁用Tarjan啊
最终，每一个串判断一遍即可。