字符串全家桶

鱼跃于渊 · 2024-02-01 11:54:14 · 算法·理论

记得写！！

[字符串前缀相关]()：

字符串后缀相关：

1. AC 自动机
2. 后缀数组
3. 后缀自动机
4. 广义后缀自动机

字符串回文相关：

1. manacher
2. 回文自动机

[字符串杂项]()：

其它的话以后有时间再补，先大致搭一个框架，下面是模板。

1.Hash（哈希）：

1.1. What：

我们定义一个把字符串映射到整数的函数 f，这个 f 称为是 hash 函数，用于判断两个字符串是否相等。

1.2. How:

竞赛中常用的是进制哈希，核心是给出一个固定进制 base，将一个串的每一个元素看做一个进制位上的数字，所以这个串就可以看做一个 base 进制的数，那么这个数就是这个串的哈希值，则我们通过比对每个串的的哈希值，即可判断两个串是否相同。
通常情况下为防止数字过大（高精度比较和直接比较字符串时间复杂度都是 O(n) 的），我们需要取模，为减少哈希碰撞的概率，模数一般为质数。常用的方法是自然溢出、单模数、双模数。

1.3. Code：

代码略。

2.Trie（字典树）：

2.1. What：

字典树是一种树形结构，核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

2.2. How：

很简单，不做讲解。

2.3. Where：

1. 检索字符串
2. 维护异或极值
3. 维护异或和
4. AC 自动机
5. 可持久化

2.4. Code：

代码如下（P8306 【模板】字典树）：

#include <bits/stdc++.h>
using namespace std;
const int N=3e6+5;
char s[N];
int T,q,n,tot,t[65][N],cnt[N];
int get(char x){
    if(x>='A'&&x<='Z') return x-'A';
    else if(x>='a'&&x<='z') return x-'a'+26;
    else return x-'0'+52;
} 
void insert(char *s){
    int p=0,c,len=strlen(s+1);
    for(int i=1;i<=len;i++){
        c=get(s[i]);
        if(!t[c][p]) t[c][p]=++tot;
        p=t[c][p];
        cnt[p]++;
    }
}
int query(char *s){
    int p=0,c,len=strlen(s+1);
    for(int i=1;i<=len;i++){
        c=get(s[i]);
        if(!t[c][p]) return 0;
        p=t[c][p];
    }
    return cnt[p];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>T;
    while(T--){
        for(int i=0;i<=64;i++)
            for(int j=0;j<=tot;j++)
                t[i][j]=0;
        for(int i=0;i<=tot;i++) cnt[i]=0;
        tot=0;
        cin>>n>>q;
        while(n--){
            cin>>(s+1);
            insert(s);
        }
        while(q--){
            cin>>(s+1);
            cout<<query(s)<<'\n';
        }
    }
    return 0;
}

3. KMP：

3.1. Code：

代码如下（P3375 【模板】KMP）：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,m,nxt[N];
char s[N],t[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>(s+1)>>(t+1);
    n=strlen(s+1);m=strlen(t+1);
    for(int i=2,j=0;i<=m;i++){
        while(j&&t[j+1]!=t[i]) j=nxt[j];
        if(t[j+1]==t[i]) j++;
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=n;i++){
        while(j&&t[j+1]!=s[i]) j=nxt[j];
        if(t[j+1]==s[i]) j++;
        if(j==m) cout<<(i-m+1)<<'\n';
    }
    for(int i=1;i<=m;i++)
        cout<<nxt[i]<<" \n"[i==n];
    return 0;
}

补KMP基本思想和做法，以及 border

4. 失配树

4.1. Code：

代码如下（P5829 【模板】失配树）：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5; 
char s[N];
int n,m,lg[N],fa[30][N],dep[N];
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=lg[dep[u]-dep[v]];~i;i--)
        if(dep[fa[i][u]]>=dep[v]) u=fa[i][u];
    for(int i=lg[dep[u]];~i;i--){
        if(fa[i][u]==fa[i][v]) continue;
        u=fa[i][u];
        v=fa[i][v];
    }
    return fa[0][u];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>(s+1)>>m;n=strlen(s+1);
    dep[1]=1;
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int i=2,j=0;i<=n;i++){
        while(j&&s[j+1]!=s[i]) j=fa[0][j];
        if(s[j+1]==s[i]) j++;
        fa[0][i]=j;
        dep[i]=dep[j]+1;
    }
    for(int i=1;i<=lg[n];i++)
        for(int j=1;j<=n;j++)
            fa[i][j]=fa[i-1][fa[i-1][j]];
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        cout<<lca(u,v)<<'\n';
    }
    return 0;
}

5. 扩展 KMP/exKMP（Z 函数）

5.1. Code：

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

#include <bits/stdc++.h>
using namespace std;
const int N=2e7+5;
char p[N],s[N];
int pl,sl,z[N],ext[N];
long long ans1,ans2;
void getZ(){
    z[0]=pl;
    int j=0;
    while(j+1<pl&&p[j]==p[j+1]) j++;
    z[1]=j;
    for(int i=2,k=1;i<pl;i++){
        if(i+z[i-k]<k+z[k]) z[i]=z[i-k];
        else{
            j=max(k+z[k]-i, 0);
            while(j+i<pl&&p[j]==p[j+i]) j++;
            z[i]=j;
            k=i;
        }
    }
}
void exkmp(){
    getZ();
    int j=0;
    while (j<pl&&j<sl&&p[j]==s[j]) j++;
    ext[0]=j;
    for(int i=1,k=0;i<sl;i++) {
        if(i+z[i-k]<k+ext[k]) ext[i]=z[i-k];
        else{
            j=max(k+ext[k]-i,0);
            while(j<pl&&j+i<sl&&p[j]==s[j+i]) j++;
            ext[i]=j;
            k=i;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>s>>p;
    sl=strlen(s);
    pl=strlen(p);
    exkmp();
    for(int i=0;i<pl;i++)
        ans1^=1LL*(i+1)*(z[i]+1);
    for(int i=0;i<sl;i++)
        ans2^=1LL*(i+1)*(ext[i]+1);
    cout<<ans1<<'\n'<<ans2<<'\n';
    return 0;
}

补思路

6. 子序列自动机：

6.1. What：

子序列自动机，顾名思义，用于多次子序列匹配。

6.2. How：

我们对于每种字符，开个数组记录一下它在哪些地方出现过，然后对于待匹配串的所有字符，一一匹配，保证位置比上一次的位置靠后，使用二分查找。

6.3. Code：

代码如下（P5826 【模板】子序列自动机）：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int type,n,q,m,L,flag,b[N];
vector <int> e[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>type>>n>>q>>m;
    for(int i=1,j;i<=n;i++){
        cin>>j;
        e[j].push_back(i);
    }
    while(q--){
        cin>>L;flag=1;
        for(int i=1;i<=L;i++) cin>>b[i];
        for(int i=1,l=0;i<=L;i++){
            auto r=upper_bound(e[b[i]].begin(),e[b[i]].end(),l);
            if(r==e[b[i]].end()){
                flag=0;
                break;
            }
            l=*r;
        }
        cout<<(flag?"Yes\n":"No\n");
    }
    return 0;
}