HASH
一个能将O(n)O(n)O(n)比较转化为O(1)O(1)O(1)的高效方法，本质上是将字符串转化为ppp进制数（通常为133311333113331等）为避免冲突一般这样设定，当然本文章不讨论有关冲突问题，还是说一个吧（ber。而且我一般在代码中用单模数HashHashHash时一般用unsignedunsignedunsigned longlonglong longlonglong自然溢出，双模数HashHashHash视情况。
H(s)=∑i=1lensiplen−iH(s) = \sum_{i=1}^{len} {s_i p^{len-i}}H(s)=∑i=1len si plen−i
并且我们得知一个前缀HHH值，我们可以求出区间HHH值：
H(L,R)=H(R)−H(L−1)×pr−l+1H(L,R) = H(R) - H(L-1) \times p^{r-l+1}H(L,R)=H(R)−H(L−1)×pr−l+1
如何卡掉一个自然溢出的HashHashHash？
这就是有名的Thue−MorseThue-MorseThue−Morse序列卡自然溢出：
定义S0=aS_0=aS0 =a，T0=bT_0=bT0 =b，令Si=Si−1+Ti−1S_i=S_{i-1}+T_{i-1}Si =Si−1 +Ti−1 ，Ti=Ti−1+Si−1T_i=T_{i-1}+S_{i-1}Ti =Ti−1 +Si−1 即可。
为什么能卡掉？我们考虑从差值下手
i=1i=1i=1：Hash(S1)−Hash(T1)=(a−b)(base−1)Hash(S_1)-Hash(T_1)=(a-b)(base-1)Hash(S1 )−Hash(T1 )=(a−b)(base−1)
i=2i=2i=2：Hash(S2)−Hash(T2)=(a−b)(base−1)(base2−1)Hash(S_2)-Hash(T_2)=(a-b)(base-1)(base^2-1)Hash(S2 )−Hash(T2 )=(a−b)(base−1)(base2−1)
.......
因为常见的basebasebase都用质数，除了222都是奇数，所以(base-1)为偶数，以此类推后面都为偶数，即都包含至少一个222的因子。当nnn仅仅为15个左右，222的因子至少都有646464个，溢出后为000，被定义为相等，这样就卡掉了自然溢出。
HASH KILLER I
如何让长度为lll的子串匹配错误，我们可以认为定义l=8192=213l=8192=2^{13}l=8192=213，代码中滑动窗口取出+排序去重，一定会错误，这样就处理好了。
那怎么生成长10510^5105长度的Thue−MorseThue-MorseThue−Morse序列呢？
这里直接给结论：aaa和bbb分布完全取决于当前这个位置二进制数中111个数的奇偶性，若为奇则为aaa，bbb反之。
当然你直接拼接一样能过。。。
那如果模数为109+710^9+7109+7怎么办，分两种情况：
1.basebasebase固定，根据生日悖论，MMM个状态找到一对相同的，大约需要M\sqrt{M}M 个数据即可，本地跑到错误数据Hack即可；
2.basebasebase纯随机，方法更简单，随机长度10510^5105的aaa，bbb随机出现的串即可。为什么对：我们人为设定Len=2×104Len=2 \times 10^4Len=2×104，那么总共有K=8×104K=8 \times 10^4K=8×104个，两两对比有(8×104)22≈3.2×109\frac {(8 \times 10^4)^2}{2} \approx 3.2 \times 10^92(8×104)2
≈3.2×109，模数为109+710^9+7109+7，期望次数大约为3.23.23.2次，根据泊松分布，P=1−e−3.2≈95.9P=1-e^{-3.2} \approx 95.9P=1−e−3.2≈95.9%。
HASH KILLER II
当然我第一发WA了一个点（碰到了4.14.14.1%的失败概率，我是不是可以买彩票了？？！），多交几次，毕竟是随机数嘛。
知道完这些，我们就可以配合二分等解决一些问题了：
通配符匹配
@cjdst 别吵，我在思考！！！！（绷
注意到通配符的个数不超过101010，我们可以在原串上拆分成 ≤21\le 21≤21串为∗*∗，???，和纯字符串，记为TokenTokenToken。
再考虑一个dpi,jdp_{i,j}dpi,j 表示主串前iii个TokenTokenToken能不能和模式串前jjj个字符。
接着就可以思考转移了：
1.第iii个TokenTokenToken为???，强制匹配第jjj个字符：dpi,j=dpi−1,j−1dp_{i,j}=dp_{i-1,j-1}dpi,j =dpi−1,j−1 。
2.第iii个TokenTokenToken为∗*∗，可以匹配或者继承j−1j-1j−1的状态以继续匹配更多字符：dpi,j=dpi−1,jdp_{i,j}=dp_{i-1,j}dpi,j =dpi−1,j OROROR dpi,j−1dp_{i,j-1}dpi,j−1 。
3.第iii个TokenTokenToken为纯字符串，直接HashHashHash判断就行：
dpi,j=dpi−1,j−lendp_{i,j}=dp_{i-1,j-len}dpi,j =dpi−1,j−len ANDANDAND Hash(S,j−len+1,j)==H(i)Hash(S,j-len+1,j)==H(i)Hash(S,j−len+1,j)==H(i)
最后答案是dpcntToken,mdp_{cntToken,m}dpcntToken,m 即可。
DNA
比较经典的二分+Hash题目，枚举起点iii，二分长度，遇到匹配不上就跳过继续二分，最多匹配不上3次，若合法匹配整个模式串答案+1+1+1。
时间复杂度O(Tnlogn)O(T n \log n)O(Tnlogn)，显然跑不满，稳过。
代码好写捏：
CF580E KEFA AND WATCH
一道线段树维护Hash的肥肠有意思的题目。
先考虑最先的问题，如何判断一个字符串是否有周期***？
这直接给结论：判断S[L+d,R]S[L+d,R]S[L+d,R]是否等于S[L,R−d]S[L,R-d]S[L,R−d]即可，证明我感觉有点复杂，就不说了（蒻。
考虑带修，区间覆盖+区间查询，考虑用线段树维护Hash。
upupup怎么做？观察H(s)H(s)H(s)的计算方式，合并左右子树时，得到H(rt)=H(ls)∗prs.len+H(rs)H(rt)=H(ls)*p_{rs.len}+H(rs)H(rt)=H(ls)∗prs.len +H(rs)。
区间覆盖怎么做？当我们修改[l,r][l,r][l,r]时，覆盖值为ccc，发现一段区间[x,y][x,y][x,y]被其完全覆盖：
H([x,y])=∑i=0len−1c∗Pi=c∗∑i=0len−1PiH([x,y])=\sum_{i=0}^{len-1} {c*P^i}=c*\sum_{i=0}^{len-1} {P^i}H([x,y])=∑i=0len−1 c∗Pi=c∗∑i=0len−1 Pi，len=y−x+1len=y-x+1len=y−x+1
所以我们可以预处理sumpi=∑j=0i−1Pisump_i= \sum_{j=0}^{i-1} {P^i}sumpi =∑j=0i−1 Pi即可，这样我们就做完了。
但是codeforces卡自然溢出HashHashHash，（怒！
所以用了双模数过的：
KMP
一个高效O(n)O(n)O(n)单模式串匹配的工具。
主要思路是用nxtinxt_inxti 记录S[1...i]S[1...i]S[1...i]的最长相等的真前缀和真后缀（真前后缀比其普通前后缀不包含本身），每次在jjj失配不用从头开始跳，从nxtjnxt_jnxtj 开始匹配。
有个重要结论：如果一个字符串长度为NNN，则这个字符串最小循环节为N−nxtNN-nxt_NN−nxtN （前提为NNN modmodmod (N−nxtN)=0(N-nxt_N)=0(N−nxtN )=0）
贴个模版代码：
接下了开始应用咯~
CENSORING S
做完这道会对KMPKMPKMP有一个更深的理解。
核心就是：每次匹配成功，我们把jjj移到匹配成功位置的前一个字符所在模式串匹配的nxtnxtnxt最大位置，用一个ftift_ifti 记录即可，前面删除操作用栈维护即可。
CF2205E
一道非常有思维含量的题目，建议先思考，这个题我在这个帖子讲。
KMP凸包专题中考虑同构的问题
好题好题！！（lyy为什么没有场切？）直接传送即可食用。鬼知道这道题代码调了多久，结果是数组大小写错了（
MANACHER
O(n)O(n)O(n)求最长回文串的工具。
核心思想就是在字符串中间加'#'号使其为偶数，再维护中心点CCC和右边界RRR,利用前面处理出来的现成值更新现在的值（要受限于当前维护的区间），最后再暴力匹配，能将复杂度降到O(n)O(n)O(n)。
pip_ipi 代表新的字符串的最长回文半径，Ans=maxi=1npi−1Ans=max_{i=1}^{n} {p_i-1}Ans=maxi=1n pi −1（可以想想为什么）。
模版：
ABB
非常简单的ManacherManacherManacher应用，只是要把边界判清楚。
先跑一遍ManacherManacherManacher，再枚举新串中的每个位置，判断对应到原串中（有可能是空，要判清楚）是否以这个点为中心的回文串延伸到最右端，如果是取最大值即可。
[POI 2010] ANT-ANTISYMMETRY
也比较简单，只用在跑ManacherManacherManacher时更改一下判断条件，用一个chkchkchk即可解决：
最长双回文串
开始有难度了......
我们会发现，当我们跑ManacherManacherManacher时所添加的'#'正好是分割双回文串的工具，所以我们维护一个LiL_iLi 表示以iii为左边界，向右的最长回文串，RiR_iRi 反之，每次跑出一个pip_ipi 顺带更新。
当然这还没结束，因为跑ManacherManacherManacher只能处理最大边界，那内部的咋办？
观察回文串的性质，以LiL_iLi 为例，如果往右缩小222格，回文串的长度−2-2−2，RiR_iRi 方向与之相反，这样我们就处理完所有LiL_iLi 和RiR_iRi 。
最后Ans=maxi=3len−2Li+RiAns=max_{i=3}^{len-2} {L_i+R_i}Ans=maxi=3len−2 Li +Ri 即可（显然111和lenlenlen不能当分割，因为左/右两边没有合法串）。
ACAM
被迫先去写计算几何（悲
PAM
被迫先去写计算几何（悲
SA
被迫先去写计算几何（悲
（为什么没有SAMSAMSAM呢，那当然是我不会啦！）
