trie 树

字符串匹配时最常见的需求，究极算法是 KMP，用于两个字符串进行匹配，而多字符串的匹配，就有多种技术：Trie 树、有限自动机。。。

Trie 树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个 26 叉树，数字的字典树是一个 10 叉树。主要思想是利用字符串的公共前缀来节省存储空间并实现快速搜索。

它有 3 个基本性质：

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
• 每个节点的所有子节点包含的字符都不相同。

基本操作包括：

• 插入节点
• 删除节点
• 查找结点（或公共前缀）

复杂度分析：

• 插入和查找的时间复杂度均为 O(n) n 为字符串长度
• 空间复杂度为 26^n，可以使用双数组实现改善 双数组 Trie 解析（真的看不下去了）

应用：

1. 字符串检索
2. 字符串最长公共前缀
3. 排序（字典顺序输出）
4. 后缀树、AC 自动机的基础

例题：

1. 给定 100000 个长度不超过 10 的单词。对于每一个单词，判断是否出现过，如果出现过，第一次出现的位置。
2. 有一个 1G 大小的一个文件，里面每一行是一个词，词的大小不超过 16 字节，内存限制大小是 1M。返回频数最高的 100 个词。
3. 1000 万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？
4. 寻找热门字符串

代码：

联系我