串子(待补)

写在前面

这个是自己看到，你看不懂请寻找oiwiki，见谅）

正文：

简单的几笔带过了。

hash

简单来说就是字符串的映射。
把一个字符串用一个值表示出来。
可以在一定范围内用 hash 方法确定唯一值。
最重要的就是两句话

1. 在 Hash 函数值不一样的时候，两个字符串一定不一样；
2. 在 Hash 函数值一样的时候，两个字符串不一定一样.

在求hash值的时候
建议双hash，或自然溢出，或hash_table。
一般定义 hash 函数：
\(Hash(s)=(\sum^n_{i=1}s_i\times b^{n-i})mod \ \ \ M\)
其中 M 是大模数，b是底数，通过这个可以前缀和获得一段区间的Hdash值。
应用：

1. 快速判定字串是否相同。（前缀和记录hash值判等）
2. 允许 𝑘 次失配的字符串匹配。
   hash+二分，对于每次失败后找一个 k 范围内的合法匹配位置。最多作k次。
3. 最长回文子串，枚举对称点后二分长度判最大。

KMP

其实KMP的思想很简单,就是建立前缀最长匹配数组,然后在字符串匹配时通过最大前缀数组优化转移

这个是建出前缀数组,先在不匹配时跳前缀的前缀数组,再在匹配后以此更新当前点的前缀数组

这个是利用前缀数组求取最大匹配,当kmp到最后长度后跳出去记录答案

trie

可以看作是一颗前缀树，常数为字符集的大小。
是AC自动机顶梁柱，异或领域的翻天蟒，听闻有一至今不会的压位trie技巧优化，反正很厉害

AC自动机

EXKMP

马拉车

SA

SAM

后缀树

PAM

也是听到回文树了）
代码实现很简单，重要的是思想
考虑一个回文串的处理，可以看作是一个回文串左右分别加上两个相同的字符
维护最长回文后缀，就可以维护出所有的回文字串
首先第一个性质，回文串有奇串和偶串，所以需要两个根作为奇串根和偶串根
然后我们可以维护fail指针，表示这个回文串的最长回文后缀
特别的，我们定义初始奇根和偶根的fail都指向奇根
然后定义奇根的长度为-1，这样fail找到奇根就知道直接连奇根了

现在我们依次插入字符串 babbab

1. 插入字符b
   从1号odd根结点出发，发现只能直接接上根结点
   fail就是从fail往上跳fail，找到偶根
   
2. 插入字符a
   从结点b出发，向上跳fail发现找到奇根，没有对应的儿子，创建新的结点
   fail 同理应连向偶根
   
3. 插入字符b
   从结点a出发，向上跳fail发现有一个和自己一样的儿子，形成新的回文串
   fail指向b
4. 插入结点b

慢慢写吧,希望今年可以写完