Trie

yyyz07 · 2018-09-05 21:24:35 · 个人记录

原理：

　　安利两个写的特好的博文：

　　https://www.cnblogs.com/TheRoadToTheGold/p/6290732.html

　　http://www.cnblogs.com/binyue/p/3771040.html

　　 以插入和查询小写字母单词为例：

　　 1.字典树用边来表示字母，并非节点储存字母。

　　 2.有相同前缀的单词则共用前缀。

　　 3.树根是一个虚点(空节点),便于查找和插入。

　　 4.每次的单词的末尾有一个标记，表示此处是一个完整的单词的结尾。

常见应用：　

　　　1.字符串查找

　　　2.求字符串的最长公共前缀

　　　3.排序

　　　4.与位运算( 异或^ 与|)相结合

下面主要通过例题来讲解应用4：

　　1.Little Xor

　　原题: https://www.luogu.org/problemnew/show/CF252A

　　题解: https://www.luogu.org/blog/yyyz05/solution-cf252a　　　　

　　这一题因为数据很弱，可以直接模拟。

　 升级版：

　　https://blog.csdn.net/SDU_Phonism/article/details/12913129

　　2.Xor Sum

　　原题：http://acm.hdu.edu.cn/showproblem.php?pid=4825