字典树 Trie

字典树（Trie）是一种基本的字符串数据结构，通常用于存储与查找字符串。

模板：P2580 于是他错误的点名开始了

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int nxt[N][26],cnt;
bool vis[N],exist[N];
void init() {
    memset(nxt,0,sizeof(nxt));
    memset(vis,0,sizeof(vis));
    cnt=0;
    return;
}
void insert(const string &s) {
    int cur=1;
    for(auto c : s) {
        if(!nxt[cur][c-'a']) {
            nxt[cur][c-'a']=++cnt;
        }
        cur=nxt[cur][c-'a'];
    }
    exist[cur]=1;
    return;
}
int find(const string &s){
    int cur=1;
    for(auto c : s) {
        if(!nxt[cur][c-'a']) {
            return 0;
        }
        cur=nxt[cur][c-'a'];
    }
    if(!exist[cur]) return 0;
    if(vis[cur]) return 1;
    vis[cur]=1;
    return 2;
}
int n,m;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    init();
    cin>>n;
    for(int i=1;i<=n;i++) {
        string s;
        cin>>s;
        insert(s);
    }
    cin>>m;
    for(int i=1;i<=m;i++) {
        string s;
        cin>>s;
        int flag=find(s);
        if(flag == 0) {
            cout<<"WRONG\n";
        }
        else if(flag == 1) {
            cout<<"REPEAT\n";
        }
        else {
            cout<<"OK\n";
        }
    }
    return 0;
}

KMP算法

kmp算法（Knuth-Morris-Pratt字符串查找算法）是一种用于在文本串 $s$ 中快速查找模式串 $p$ 的算法。

我们定义 $pmt[i]$ 为 $[p_0,p_1,p_2,…,p_i]$ 的最大相同前后缀（border）的长度（前后缀不能等于原串自身）。

利用 $pmt$ 数组，我们可以在线性时间内完成字符串查找问题。具体的，我们用两个指针 $i,j$ ，当 $s_i$ 与 $p_j$ 匹配时，两个指针正常向后移动；当 $s_i$ 与 $p_j$ 不匹配时，我们直接让指针 $j$ 跳到 $pmt[j-1]$ 的位置即可。原理见下图：

现在只剩下如何求出 $pmt$ 数组这一个问题了。直接暴力匹配的复杂度显然不可接受，但我们有一个非常巧妙的办法，模拟之前核心算法的过程，让 $p$ 串错开一位后自己匹配自己。

模板：P3375 【模板】KMP

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
string s,p;
int pmt[N];
void init() {
    for(int i=1,j=0;i<p.size();i++) {
        while(j && p[i] != p[j]) j=pmt[j-1];
        if(p[i] == p[j]) j++;
        pmt[i]=j;
    }
}
void kmp() {
    for(int i=0,j=0;i<s.size();i++) {
        while(j && s[i] != p[j]) j=pmt[j-1];
        if(s[i] == p[j]) j++;
        if(j == p.size()) {
            cout<<i-j+2<<"\n";
            j=pmt[j-1];
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);   
    cin>>s>>p;
    init();
    kmp();
    for(int i=0;i<p.size();i++) {
        cout<<pmt[i]<<" ";
    }
    return 0;
}

Z算法/拓展KMP算法

Z算法（Z-Algorithm）是一种字符串算法，在国内也常常被叫做拓展KMP算法。它可以在线性时间内求出文本串 $s$ 的所有后缀与模式串 $t$ 的最长公共前缀（LCP）。

首先我们定义一个字符串 $s$ 的Z函数。我们设 $Z(i)$ 为 $s$ 与 $[s_i,s_{i+1},…,s_{n-1}]$ 的最长公共前缀。假设 $Z(i) \neq 0$ ，那么我们定义 区间$[i,i+Z(I)-1]$ 为一个 Z-box，也就是说，一个Z-box是整个字符串的一个前缀。

我们枚举从左向右枚举 $i$ ，同时维护 $l$ 与 $r$ ，其中 $[l,r]$ 表示 $l \leq i$ 且 $r$ 最大的Z-box.下面我们进行分类讨论：

• $r<i$ ，说明当前Z-box对 $i$ 的答案没有影响，我们直接从 $i$ 开始向后暴力匹配计算$Z(i)$
• $r \geq i$，因为$[s_0,s_1,…s_{r-l}]$ 与 $[s_l,…，s_r]$ 相等，所以 $[s_i,…,s_r]$ 与 $[s_{i-l},…,s_{r-l}]$ 也相同，考虑 $Z(i-l)$ ，如果从 $i-l$ 开始的Z-box没有超出 $r-l$ ，我们直接有 $Z(i) = Z(i-l)$ ；如果超出了，因为我们已经确定 $[s_i,…,s_r]$ 是一个Z-box的一部分，我们像第一种情况一样从 $r$ 开始向后暴力匹配即可。

而对于原问题，设$ ‘\$’ $为给定字符集外字符，我们可以求出字符串 $ p+’\$’+s $ 的Z函数，根据Z函数的定义，$s$ 的后缀 $[s_i,…,s_{n-1}] $ 与 $t$ 的LCP为 $Z(i+n+1)$。

模板：P5410 【模板】扩展 KMP/exKMP（Z 函数）

代码：

//PS：洛谷的模板题需要开long long
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=2e7+10;
string a,b,c;
int z[N*2];
LL ans1,ans2;
void exkmp() {
    LL n=b.size();
    z[0]=n;
    ans1=z[0]+1;
    for(int i=1,l=0,r=0;i<c.size();i++) {
        if(z[i-l] < r-i+1) z[i]=z[i-l];
        else {
            z[i]=max(r-i+1,0);
            while(i+z[i] < c.size() && c[z[i]] == c[i+z[i]]) z[i]++;
            l=i, r=i+z[i]-1;
        }
        if(i < b.size()) ans1=ans1^((i+1)*(1+z[i]));
        if(i > b.size()) ans2=ans2^((i-b.size())*(1+z[i]));
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);   
    cin>>a;
    cin>>b;
    c=b+'$'+a;
    exkmp();
    cout<<ans1<<"\n"<<ans2<<"\n";
    return 0;
}

Manacher算法

Manacher算法主要用于求解字符串的回文子串问题。具体的，Manacher算法会求解出一个 $d$ 数组，$d[i]$ 表示以 $s[i]$ 为中心的奇回文子串的数量。而偶回文子串，我们可以通过向相邻字符之间以及字符串的首尾处添加给定字符集外元素，将偶回文子串转化为奇回文子串。

Manacher算法的具体流程与Z算法类似。我们从右向左枚举 $i$，并维护 $l$ 与 $r$ ，使得 $[s_l,s_{l+1},…,s_r]$ 是满足 $l \leq i$ 且 $r$ 最大的回文子串。枚举到一个新的 $i$ 时，我们进行分类讨论：

• 如果 $i > r$ ，暴力计算 $d[i]$ ，并更新 $l$ 与 $r$.
• 如果 $i \leq r$ ，找到 $i$ 关于 $[s_l,s_{l+1},…,s_r]$ 中心的对称点 $j$ ，如果以 $j$ 为中心的最长回文子串的左端点大于 $l$ ，则直接有 $d[i] = d[j]$
• 如果以 $j$ 为中心的最长回文子串的左端点小于 $l$，则我们在尽可能的将 $l,r$ 尽可能地向两端扩展并更新。

模板：P3805 【模板】manacher

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=11000010;
string a;
string s;
int d[N*2],ans;
void manacher() {
    for(int i=0,l=0,r=-1;i<s.size();i++) {
        if(i > r) {
            while(i-d[i] >=0 && i+d[i] < s.size() && s[i+d[i]] == s[i-d[i]]) d[i]++;
            l=i-d[i]+1; r=i+d[i]-1;
        }
        else {
            int j=l+r-i;
            if(j-d[j] >= l) d[i] = d[j];
            else {
                d[i]=j-l+1;
                while(i-d[i] >=0 && i+d[i] < s.size() && s[i+d[i]] == s[i-d[i]]) d[i]++;
                l=i-d[i]+1; r=i+d[i]-1;
            }
        }
        ans=max(ans,d[i]);
    }
    cout<<ans-1<<"\n";
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);  
    cin>>a;
    s+='$';
    for(int i=0;i<a.size();i++) {
        s+=a[i]; s+='$';
    }  
    manacher();
    return 0;
}