Trie 魏楚.

Presentation on theme: "Trie 魏楚."— Presentation transcript:

1 trie 魏楚

2 trie简介 取自retrieval/rɪˈtri:vl/（检索） 发明者Edward Fredkin 音同try 字典树/前缀树 DFA

3 结构 根 节点 单词(ASP)

4 节点结构 指针数组 挂链表 左儿子右兄弟

5 建树 an ant angry big

6 应用 检索 排序 字符串匹配 最长公共前缀 其他

7 一、检索 有道搜索框(tyvj 1228) 给定前缀 输出前8个符合的单词

8 一、检索 按输入顺序（比如已按热度排序）——挂链表 按字典序——指针数组

9 二、排序 字符串排序 快排/归并 trie 比较次数O(NlgN) 每次比较最坏O(L) 总复杂度O(NLlgN) 建树O(NL)
DFS O(NL) 总复杂度O(NL)

10 二、排序 整数排序 将所有数用二进制表达即可建树 时间复杂度O(N) 常数略大

11 三、字符串匹配 N个小字符串，最长长度为M，母串长度L，要求找出所有匹配位置 KMP O(NM + NL) trie O(NM + ML)

12 四、最长公共前缀 字符串最长公共前缀 Cow XOR

13 字符串最长公共前缀 给出N个小写字母字符串，有Q个询问，每次询问第i个和第j个字符串的最长公共前缀长度 一种解法：
建字典树，记录节点深度，转为LCA问题 倍增LCA Tarjan LCA 转RMQ，ST算法

14 Cow XOR 给定N个整数a[1]~a[N](0 ≤ a[i] ≤ 221 - 1) 需要找到一个区间[l,r]，满足：
a[l] xor a[l + 1] xor a[l + 2] xor …… xor a[r]最大 在满足上一条的情况下r最小 在满足上一条的情况下l最大 (来源：USACO Training Chapter 6)

15 Cow XOR 注意到a ^ b ^ a = b 记f(l,r)为a[l] ^ a[l + 1] ^ … ^ a[r]，令a[0] = 0，则有f(l,r) = f(0,r) ^ f(0,l – 1) 题目很容易转化为求l和r，使得b[l] ^ b[r]最大

16 Cow XOR 贪心 例子 0010 0011 0101 0111 1001

17 五、其他 trie + KMP = AC自动机 词典 快速查询 中文分词

18 trie的缺点及优化方案 缺点 空间占用大（尤其是字符集大的时候） 优化方案 三数组trie 双数组trie

19 双数组trie简介 将trie视为DFA 维护两个整数数组base[]和check[] 状态s读入字符c转移到状态t，当且仅当
base[s]+c=t check[t] =s

20 参考资料 董华星《浅析字母树在信息学竞赛中的应用》，IOI2009国家集训队论文 wiki的trie词条
An Implementation of Double-Array Trie

21 Q&A 谢谢大家！