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