背景复健次日本来想接着做连通图结果调一个题调了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.相信自己是天命之子(慎用)代码#includebits/stdc.husingnamespacestd;#definelllonglong#defineB233#defineM100000007intgethash(string s){intans0;for(charc:s){ans(ans*Bc)%M;}returnans;}setints;signedmain(){intn;string st;cinn;for(inti1;in;i){cinst;s.insert(gethash(st));}couts.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]个字符串以它为前缀。另外由于空间限制本题需要离散化。代码#includebits/stdc.husingnamespacestd;#defineN3000006inta[N][62],cnt[N];intT,n,q,idx;string s;intfind(charc){//离散化if(isdigit(c))returnc-0;if(isupper(c))returnc-A10;if(islower(c))returnc-a36;}voidinsert(string s){intpos0;for(charch:s){intcfind(ch);if(!a[pos][c])a[pos][c]idx;posa[pos][c];cnt[pos];}}intquery(string s){intpos0;for(charch:s){intcfind(ch);if(!a[pos][c])return0;posa[pos][c];}returncnt[pos];}intmain(){cinT;while(T--){idx0;cinnq;for(inti1;in;i){cins;insert(s);}for(inti1;iq;i){cins;coutquery(s)endl;}for(inti0;iidx;i){for(intj0;j62;j)a[i][j]0;}for(inti1;iidx;i)cnt[i]0;//用memset清空数组会爆炸哦}return0;}三、马拉车(M a n a c h e r \pmb{Manacher}Manacher)模板P3805M 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 i12i12时m a x r 15 maxr15maxr15)2.m i d midmid表示当前最长回文串的中间项下标(如i 12 i12i12时m i d 8 mid8mid8)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 i12i12为例对此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-i1maxr−i1则一定可以拓展到。(因为回文串内是对称的)反之则一定不能拓展到因为不保证m a x r maxrmaxr右边字符仍对称此时p [ i ] p[i]p[i]的最大值为m a x r − i 1 maxr-i1maxr−i1。代码#includebits/stdc.husingnamespacestd;#defineN11000005intp[2*N];//记得乘2string s#,s1;intmain(){cins1;for(charc:s1){s.push_back(c);s.push_back(#);//不能用加法因为加法是O(n)的}intmaxr0,mid0,ans0;for(inti0;is.size();i){if(imaxr)p[i]min(p[mid*2-i],maxr-i1);elsep[i]1;while(ip[i]ip[i]s.size()s[ip[i]]s[i-p[i]])p[i];//暴力拓展if(ip[i]-1maxr){maxrip[i]-1;midi;}//更新ansmax(ans,p[i]*2-1);}coutans/2;//最终答案return0;}继续战斗