一、首先理解字符串操作的意义：
没意义（雾
其实字符串操作的意义是很浅显的，比如百度的推荐搜索啊，比如查找比对一篇题解里有多少个相同或者不同的脏字然后 kkksc03 再根据其数量、恶劣程度决定用多大的刀将博主 kill 掉。。。所以字符串操作很重要啊喂 qwq 。
再来考虑时间：如果百度对于一个人的一次“常搜”推荐需要 10s ，那么对于全国网友来说，同时上网的人群基数很高，那么如果服务器性能不好的话，怕不是要三星 note7？？？ qwq
所以啊，打造高效的字符串算法是很有必要滴！
二、言归正传，浅析字符串哈希
哈希其实是所有字符串操作中，笔者认为最简单的操作了（except输入输出qwq）。哈希的过程，其实可以看作对一个串的单向加密过程，并且需要保证所加的密不能高概率重复（就像不能让隔壁老王轻易地用它家的钥匙打开你家门一样qwq），通过这种方式来替代一些很费时间的操作。
比如，最常见的，当然就是通过哈希数组来判断几个串是否相同（洛谷P3370）。此处的操作呢，很简单，就是对于每个串，我们通过一个固定的转换方式，将相同的串使其的“密”一定相同，不同的串 尽量 不同。
此处有人指出：那难道不能先比对字符串长度，然后比对ASCLL码之和吗？事实上显然是不行的（比如ab和ba，并不是同一个串，但是如是做却会让其认为是qwq）。这种情况就叫做** hash 冲突**，并且在如此的单向加密哈希中， hash 冲突的情况在所难免（bzoj就有这种让你给出一组样例，使得一段哈希代码冲突的题，读者可以尝试尝试）。
而我们此处介绍的，即是最常见的一种哈希：进制哈希。进制哈希的核心便是给出一个固定进制 base ，将一个串的每一个元素看做一个进制位上的数字，所以这个串就可以看做一个 base 进制的数，那么这个数就是这个串的哈希值；则我们通过比对每个串的的哈希值，即可判断两个串是否相同
奉上 P3370ac 代码（单哈希）：
当然，再好的哈希也会有冲突，此时有两种做法可以解决或者降低哈希冲突的可能性
1、无错哈希
其实原理很简单，就是我们要记录每一个已经诞生的哈希值，然后对于每一个新的哈希值，我们都可以来判断是否和已有的哈希值冲突，如果冲突，那么可以将这个新的哈希值不断加上一个大质数，直到不再冲突（比如somebody’s birthday qwq）。
先贴代码：
正如下图（亲手做的英文高逼格）：
2、多重哈希
这其实就是你用不同的两种或多种方式哈希，然后分别比对每一种哈希值是否相同——显然是增加了空间和时间，但也确实增加了其正确性。
下面皮一个哈希自动机qwq（不用百度了，名字自己起的）
三、字典树浅析
1、简要介绍
首先要知道，字典树是一种假想数据结构（数据结构不都是假想的吗qwq），那么问题来了——为什么是要用字典树呢？
为什么不用类似字典链表之类的东西呢？很简单，所有树形结构都有一个基本特点，就是元素与元素间的关系为继承的一对多关系。
拿字典树来说，每一个元素都可以有几个子元素，作为它之后的字母；而倘若要比对两个字符串是否相同，只需要比对在这棵字典树上，这两个串最后一个元素的祖先链(即前缀)是否相同，并且对于祖先链来说，并不用逐个比较，只需要记录访问就行。比如下图就是一棵 Trie ，这里用颜色区分单词路径上的点
2、字典树基础与如何建树（插入操作）
首先，关于字典树，我们一般不是用点来存储字符的，而是用边——为什么呢？之后再说（十分皮地卖个关子qwq）。
重新首先，一般来说，字典树是不会使用根节点的，原因很浅显，因为根节点的个数决定究竟有几棵字典树，而通常字典树是只有一棵的，否则产生森林会很麻烦（qwq你皮你就splay，并且如果有森林的话应该叫做“字典森林”啊喂）。
但是我们要知道，并不是一个题中所有的串都有公共前缀（肯定不会的吧qwq），可如果根节点唯一，就代表他们一定有公共前缀，并且公共前缀的长度必定大于等于1。
其次，字典树中每个节点的子节点数量都肯定会小于某个数。
如果字典树里都是小写字母，那么“某个数”就是26；如果大小写都有，“某个数”就应该是52（证明过程：显然）；
并且每个节点的所有的边都不同，这条性质可以便于我们判断在某一棵字典树到底有没有某条链：只要前缀不符合，就不需要再判断，因为必然没有（同一深度、同一父亲，边与边必定互异）
在这里，我选择用结构体来存树，具体解释见注释：
于是便可以通过这种方式比对字符串，期望时间复杂度O（n）大多用于比对。
3、关于字典树的查找
查找前缀比较好写，只需要一边判断是否符合要求，一边判断是否继续迭代即可。
其实查询单词和查询前缀差别不大，只是我们每次都需要维护一个 check[i] （ bool ），存在单词链的末尾。
每当一个新字符已经被标记时（即所查询单词的这个字母及其前缀都在树的某条链上），我们**使这个字符 check 异于它祖先们的 check *，最后判断*该条匹配链结尾字符的 check 是否异于链上其他字符的 check **即可判断是否有这个单词（如果没有的话，末尾的 check 肯定与链上其他的相同啊qwq）
至于前缀出现次数，很简单，只要将每一个前缀的出现次数存到它相连的子节点，最后输出前缀最后一个字符所带的次数即可（可以用数组维护，也可以直接写在结构体里）
好啦，就是这样，希望对大家有所帮助。
日拱一卒，功不唐捐！
本文发布于洛谷日报，特约作者：皎月半洒花
原文https://pks-loving.blog.luogu.org/zi-fu-chuan-xue-xi-bi-ji-ha-xi-hash-yu-zi-dian-shu-trie
联系客服
