)
背景
复健次日，本来想接着做连通图，结果调一个题调了3h才发现自己把i–写成i++了，AI也没发现，气得本人想当场退役，只好看看字符串来压压惊。
一、字符串哈希
模板：P3370
判断两个字符串是否相同，H a s h HashHash是个不错的方法。
试想有1 e 9 1e91e9个不同的数字，从中选出1 e 6 1e61e6个，如何判断有多少个不同的数？
我们可以将这些数分别对1 e 6 1e61e6取模，以此判断两数是否相同。
以此类推，对于字符串，我们可以把它类比为一个B BB进制数，通过逐位累加取模便可得到它的H a s h HashHash函数。
如果两个字符串的H a s h HashHash函数不同，那么它们一定不同，若相同，则它们不一定相同。
这就产生了问题：两个不同的字符串构成了相同的H a s h HashHash函数，产生了相撞。
对于最基础的哈希，有以下几种办法避免相撞：
1.将进制B BB和模数M MM调为质数(不会证明)
2.用双哈希(显而易见)
3.相信自己是天命之子(慎用)
代码
#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineB233#defineM100000007intgethash(string s){intans=0;for(charc:s){ans=(ans*B+c)%M;}returnans;}set<int>s;signedmain(){intn;string st;cin>>n;for(inti=1;i<=n;i++){cin>>st;s.insert(gethash(st));}cout<<s.size();return0;}二、字典树
模板：P8036
字典树(T r i e TrieTrie)，是一棵这样的树：
显然，每个结点都代表一个字符，这样的结构能很好地解决前缀问题。
构建字典树的过程中，需要维护三个变量：
1.i d x idxidx：字典树的结点数；
2.a [ p o s ] [ c ] a[pos][c]a[pos][c]：表示c cc字符在第p o s pospos位置时其子结点的位置；
3.c n t [ p o s ] cnt[pos]cnt[pos]：记录第p o s pospos位置出现过的字符数量。
建树时，若当前位置无字符，则更新idx，新建结点；
查询时，若当前位置无字符，则说明没有字符串以它为前缀；反之，则有c n t [ p o s ] cnt[pos]cnt[pos]个字符串以它为前缀。
另外，由于空间限制，本题需要离散化。
代码
#include<bits/stdc++.h>usingnamespacestd;#defineN3000006inta[N][62],cnt[N];intT,n,q,idx;string s;intfind(charc){//离散化if(isdigit(c))returnc-'0';if(isupper(c))returnc-'A'+10;if(islower(c))returnc-'a'+36;}voidinsert(string s){intpos=0;for(charch:s){intc=find(ch);if(!a[pos][c])a[pos][c]=++idx;pos=a[pos][c];cnt[pos]++;}}intquery(string s){intpos=0;for(charch:s){intc=find(ch);if(!a[pos][c])return0;pos=a[pos][c];}returncnt[pos];}intmain(){cin>>T;while(T--){idx=0;cin>>n>>q;for(inti=1;i<=n;i++){cin>>s;insert(s);}for(inti=1;i<=q;i++){cin>>s;cout<<query(s)<<endl;}for(inti=0;i<=idx;i++){for(intj=0;j<62;j++)a[i][j]=0;}for(inti=1;i<=idx;i++)cnt[i]=0;//用memset清空数组会爆炸哦}return0;}三、马拉车(M a n a c h e r \pmb{Manacher}Manacher)
模板：P3805
M a n a c h e r ManacherManacher算法用于解决最长回文串问题。
首先，我们向字符串开头结尾及每个字符之间加入‘#’，将回文串长度统一为奇数。
暴力方法：枚举中间项和长度，向两边拓展，最终回文串长度为l e n / 2 len/2len/2，时间复杂度O ( n 2 ) O(n^2)O(n2)。
以以下字符串为例(省略了‘#’)：
a b c e f e c b x b c e f e c b x a\ b\ c\ e\ f\ e\ c\ b\ x\ b\ c\ e\ f\ e\ c\ b\ xabcefecbxbcefecbx
在M a n a c h e r ManacherManacher算法中，需要维护以下变量：
1.m a x r maxrmaxr：表示[ 1 , i − 1 ] [1,i-1][1,i−1]个字符内可拓展到的最长回文串右边界(如i = 12 i=12i=12时m a x r = 15 maxr=15maxr=15)；
2.m i d midmid：表示当前最长回文串的中间项下标(如i = 12 i=12i=12时m i d = 8 mid=8mid=8)；
3.p [ i ] p[i]p[i]：表示第i ii个字符可向外拓展的最长长度。
显然，需要更新p [ i ] p[i]p[i]的值，考虑两种情况：
1 ◯ \textcircled 11◯p [ i ] > = m a x r p[i]>=maxrp[i]>=maxr：直接暴力向外拓展即可；
2 ◯ \textcircled 22◯p [ i ] < m a x r p[i]<maxrp[i]<maxr：依旧以i = 12 i=12i=12为例，对此，f ff一定能找到关于m i d midmid对称的另一个f ff，下标为m i d × 2 − i mid \times 2-imid×2−i，即4。
p [ 4 ] p[4]p[4]显然是计算好的，所以可以利用对称性推出p [ 12 ] p[12]p[12]。
考虑到p [ 4 ] p[4]p[4]向左拓展，对应p [ 12 ] p[12]p[12]会向右拓展。
如果p [ 4 ] p[4]p[4]不大于m a x r − i + 1 maxr-i+1maxr−i+1，则一定可以拓展到。(因为回文串内是对称的)
反之，则一定不能拓展到，因为不保证m a x r maxrmaxr右边字符仍对称，此时p [ i ] p[i]p[i]的最大值为m a x r − i + 1 maxr-i+1maxr−i+1。
代码
#include<bits/stdc++.h>usingnamespacestd;#defineN11000005intp[2*N];//记得乘2string s="#",s1;intmain(){cin>>s1;for(charc:s1){s.push_back(c);s.push_back('#');//不能用加法，因为加法是O(n)的}intmaxr=0,mid=0,ans=0;for(inti=0;i<s.size();i++){if(i<=maxr)p[i]=min(p[mid*2-i],maxr-i+1);elsep[i]=1;while(i>=p[i]&&i+p[i]<s.size()&&s[i+p[i]]==s[i-p[i]])p[i]++;//暴力拓展if(i+p[i]-1>maxr){maxr=i+p[i]-1;mid=i;}//更新ans=max(ans,p[i]*2-1);}cout<<ans/2;//最终答案return0;}继续战斗！
