背景

复健次日，本来想接着做连通图，结果调一个题调了3h才发现自己把i–写成i++了，AI也没发现，气得本人想当场退役，只好看看字符串来压压惊。

一、字符串哈希

模板：P3370
判断两个字符串是否相同，$Hash$是个不错的方法。
试想有$1e9$个不同的数字，从中选出$1e6$个，如何判断有多少个不同的数？
我们可以将这些数分别对$1e6$取模，以此判断两数是否相同。
以此类推，对于字符串，我们可以把它类比为一个$B$进制数，通过逐位累加取模便可得到它的$Hash$函数。
如果两个字符串的$Hash$函数不同，那么它们一定不同，若相同，则它们不一定相同。
这就产生了问题：两个不同的字符串构成了相同的$Hash$函数，产生了相撞。
对于最基础的哈希，有以下几种办法避免相撞：
1.将进制$B$和模数$M$调为质数(不会证明)
2.用双哈希(显而易见)
3.相信自己是天命之子(慎用)

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define B 233
#define M 100000007
int gethash(string s){
    int ans=0;
    for(char c:s){
        ans=(ans*B+c)%M;
    }
    return ans;
}
set<int> s;
signed main(){
    int n;
    string st;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>st;
        s.insert(gethash(st));
    }
    cout<<s.size();
    return 0;
}

二、字典树

模板：P8036
字典树($\text{Trie}$)，是一棵这样的树：

显然，每个结点都代表一个字符，这样的结构能很好地解决前缀问题。
构建字典树的过程中，需要维护三个变量：
1.$idx$：字典树的结点数；
2.$a[pos][c]$：表示$c$字符在第$pos$位置时其子结点的位置；
3.$cnt[pos]$：记录第$pos$位置出现过的字符数量。
建树时，若当前位置无字符，则更新idx，新建结点；
查询时，若当前位置无字符，则说明没有字符串以它为前缀；反之，则有$cnt[pos]$个字符串以它为前缀。
另外，由于空间限制，本题需要离散化。

代码

#include<bits/stdc++.h>
using namespace std;
#define N 3000006
int a[N][62],cnt[N];
int T,n,q,idx;
string s;
int find(char c){//离散化
    if(isdigit(c)) return c-'0';
    if(isupper(c)) return c-'A'+10;
    if(islower(c)) return c-'a'+36;
}
void insert(string s){
    int pos=0;
    for(char ch:s){
        int c=find(ch);
        if(!a[pos][c]) a[pos][c]=++idx;
        pos=a[pos][c];
        cnt[pos]++;
    }
}
int query(string s){
    int pos=0;
    for(char ch:s){
        int c=find(ch);
        if(!a[pos][c]) return 0;
        pos=a[pos][c];
    }
    return cnt[pos];
}
int main(){
    cin>>T;
    while(T--){
        idx=0;
        cin>>n>>q;
        for(int i=1;i<=n;i++){
            cin>>s;
            insert(s);
        }
        for(int i=1;i<=q;i++) {
            cin>>s;
            cout<<query(s)<<endl;
        }
        for(int i=0;i<=idx;i++){
            for(int j=0;j<62;j++) a[i][j]=0;
        }
        for(int i=1;i<=idx;i++) cnt[i]=0;//用memset清空数组会爆炸哦
    }
    return 0;
}

三、马拉车($\text{Manacher}$)

模板：P3805
$Manacher$算法用于解决最长回文串问题。
首先，我们向字符串开头结尾及每个字符之间加入‘#’，将回文串长度统一为奇数。
暴力方法：枚举中间项和长度，向两边拓展，最终回文串长度为$len/2$，时间复杂度$O(n^2)$。
以以下字符串为例(省略了‘#’)：
$$abcefecbxbcefecbx$$
在$Manacher$算法中，需要维护以下变量：
1.$maxr$：表示$[1,i-1]$个字符内可拓展到的最长回文串右边界(如$i=12$时$maxr=15$)；
2.$mid$：表示当前最长回文串的中间项下标(如$i=12$时$mid=8$)；
3.$p[i]$：表示第$i$个字符可向外拓展的最长长度。
显然，需要更新$p[i]$的值，考虑两种情况：
$\stackrel{◯}{1}$ $p[i]>=maxr$：直接暴力向外拓展即可；
$\stackrel{◯}{2}$ $p[i]<maxr$：依旧以$i=12$为例，对此，$f$一定能找到关于$mid$对称的另一个$f$，下标为$mid\times 2-i$，即4。
$p[4]$显然是计算好的，所以可以利用对称性推出$p[12]$。
考虑到$p[4]$向左拓展，对应$p[12]$会向右拓展。
如果$p[4]$不大于$maxr-i+1$，则一定可以拓展到。(因为回文串内是对称的)
反之，则一定不能拓展到，因为不保证$maxr$右边字符仍对称，此时$p[i]$的最大值为$maxr-i+1$。

代码

#include<bits/stdc++.h>
using namespace std;
#define N 11000005
int p[2*N];//记得乘2
string s="#",s1;
int main(){
    cin>>s1;
    for(char c:s1){
        s.push_back(c);
        s.push_back('#');//不能用加法，因为加法是O(n)的
    }
    int maxr=0,mid=0,ans=0;
    for(int i=0;i<s.size();i++){
        if(i<=maxr) p[i]=min(p[mid*2-i],maxr-i+1);
        else p[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;//最终答案
    return 0;
}

四.$\text{KMP}$

模板：P3375
$\text{KMP}$算法用于解决字符串匹配问题。

给出两个字符串 $s_1$ 和 $s_2$，若 $s_1$ 的区间 $[l,r]$ 子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现了，其出现位置为 $l$。
现在请你求出 $s_2$ 在 $s_1$ 中所有出现的位置。
定义一个字符串 $s$ 的 border 为 $s$ 的一个非 $s$ 本身的子串 $t$，满足 $t$ 既是 $s$ 的前缀，又是 $s$ 的后缀。
对于 $s_2$，你还需要求出对于其每个前缀 $s^{\prime }$ 的最长 border $t^{\prime }$ 的长度。

首先解决第二个任务。
容易知道，一个字符串的border的border仍是它的border，所以通过从最长border往下跳，就能找到它所有的border。
我们不妨假设遍历到第$i$个字符时，前面的最长border已经算好了。
也就是说，用$next[i]$表示以$i$结尾的前缀的最长border长度。(DP复现)
“转移"一下：遍历到$i$时，$next[i-1]$是确定的，此时维护一个$j$，表示前缀的结尾位置。此时只需要判断$s[i]$和$s[j+1]$是否相等。
如果$s[i]=s[j+1]$，则匹配出最长border，$next[i]=j+1$
如果$s[i]\ne s[j+1]$，则让$j$跳到$next[j]$位置，继续匹配。

接下来思考第一个任务与$next$数组有何关系。
在暴力方法中，需要逐位匹配两个字符串，如果发现不同则向右移动一位重新匹配。
现在有了$next$数组，当发现两个字符串不匹配时，直接从前缀跳到匹配的后缀位置即可。
最终的时间复杂度为$O(|s|)$。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000006
string s1,s2;
int n1,n2,nxt[N];
signed main(){
    cin>>s1>>s2;
    n1=s1.size(),n2=s2.size();
    s1=' '+s1, s2=' '+s2;
    int j=0;
    for(int i=2;i<=n2;i++){
        while(j&&s2[i]!=s2[j+1]) j=nxt[j];
        if(s2[i]==s2[j+1]) j++;
        nxt[i]=j;
    }
    j=0;
    for(int i=1;i<=n1;i++){
        while(j&&s1[i]!=s2[j+1]) j=nxt[j];
        if(s1[i]==s2[j+1]) j++;
        if(j==n2) cout<<i-n2+1<<endl;
    }
    for(int i=1;i<=n2;i++) cout<<nxt[i]<<' ';
    return 0;
}

懒得写结尾了……