ZR 集训 Day20 – 基础字符串算法

ooliver 发布于 11 小时前 74 次阅读 OI

AI 摘要

字符串算法看似基础，却藏着不少精妙设计：哈希绕开暴力匹配，KMP用前缀函数避免回溯，Manacher借助对称性优化……这些模板你真的吃透了吗？今天把六大基础串串算法重新打了一遍，带你一次性看清它们的共通之处。

前言

很久没写串串题字符串题了，并且博客上似乎也没有关于字符串的专题，所以今天把一些基础的模板重新打了一遍，放了上来。

题单

CF1200E Compress Words

字符串哈希题。

维护答案串的前缀哈希，对新加入的串做前缀哈希处理，并暴力枚举答案串后缀与新串前缀的重合长度即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
const int N=1e6+5;
const ll p=1e9+7;
const int mod=998244353;
int T,n,m;
ll a[N],b[N],mi[N];
string now="#",s;
 
void init(){
    mi[0]=1;
    for(int i=1;i<N;i++) mi[i]=mi[i-1]*p;
}
 
void solve(){
    int ans=0;
    for(int i=1;i<=m;i++) b[i]=(b[i-1]*p+s[i])%mod;
    for(int i=1;i<=min(n,m);i++){
        if(a[n]-a[n-i]*mi[i]==b[i]){
            ans=i;
        }
    }
    for(int i=ans+1;i<=m;i++){
        a[n+1]=(a[n]*p+s[i])%mod;
        now+=s[i],n++;
    }
}
 
signed main(){
    init();
    cin>>T;
    for(int i=1;i<=T;i++){
        cin>>s;
        m=s.size(),s="#"+s;
        solve();
    }
    for(int i=1;i<=n;i++) cout<<now[i];
    return 0;
}

P8306 【模板】字典树 / Trie

字典树模板，用现在的马蜂重写了一遍，封装到结构体里了。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=5e6+5;
int T,n,q;

struct TRIE{
    int idx=0;
    int trie[N][70],tag[N];
    int cti(char c){
        if(c>='a'&&c<='z') return c-'a';
        else if(c>='A'&&c<='Z') return c-'A'+26;
        else return c-'0'+52;
    }
    void clear(){
        for(int i=0;i<=idx;i++) {
            memset(trie[i],0,sizeof trie[i]);
            tag[i]=0;
        }
        idx=0;
    }
    void insert(string s){
        int p=0;
        for(int i=0;i<s.size();i++){
            if(!trie[p][cti(s[i])]) trie[p][cti(s[i])]=++idx;
            p=trie[p][cti(s[i])],tag[p]++;
        }
    }
    int check(string s){
        int p=0;
        for(int i=0;i<s.size();i++){
            if(!trie[p][cti(s[i])]) return 0;
            p=trie[p][cti(s[i])];
        }
        return tag[p];
    }
}trie;

void solve(){
    trie.clear();
    string s;
    cin>>n>>q;
    while(n--){
        cin>>s;
        trie.insert(s);
    }
    while(q--){
        cin>>s;
        cout<<trie.check(s)<<"\n";
    }
}
      
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) solve();
    return 0;
}

P3375 【模板】KMP

也是找到了一个非常简洁的写法，看代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=2e6+5;
int n,m;
int pi[N];
string a,b;

void getpi(){
    for(int i=1;i<a.size();i++){
        int j=pi[i-1];
        while(j>0&&a[i]!=a[j]) j=pi[j-1];
        if(a[i]==a[j]) j++;
        pi[i]=j;
    }
}

int main(){
    cin>>b>>a;
    n=a.size(),m=b.size();
    a=a+"#"+b;
    getpi();
    for(int i=n+1;i<=n+m;i++) if(pi[i]==n) cout<<i-2*n+1<<"\n";
    for(int i=0;i<n;i++) cout<<pi[i]<<" ";
    return 0;
}

P13270 【模板】最小表示法

简化题意：把一个字符串首位相连得到一个环，再把这个环从一处断开得到一个新的字符串，求可能得到的新字符串中字典序最小的那一个。

详细步骤看代码中的注释：

C++
#include<bits/stdc++.h>
using namespace std;

int zxbsf(int n,string s){
    int i=0,j=1,k=0;//维护 i,j 两个指针以及当前匹配长度 k
    while(i<n&&j<n&&k<n){//保证不越界
        if(i==j) j++;//如果指针重合，则避让
        if(s[(i+k)%n]>s[(j+k)%n]) i+=k+1,k=0;//如果 j 指针更优，则把 i 移到失配位置的后一位，保证最优解
        else if(s[(i+k)%n]<s[(j+k)%n]) j+=k+1,k=0;//同理
        else k++;//否则继续匹配
    }
    return min(i,j);//最后指针最小的那一个就是答案
}

int main(){
    int n;
    string s;
    cin>>n>>s;
    int id=zxbsf(n,s);
    for(int i=0;i<n;i++) cout<<s[(i+id)%n];
    return 0;
}

P3805 【模板】Manacher

做过的板子题，在相邻字符中间添加辅助字符的思路非常妙。

大致思路：用一个数组记录以当前点为对称中心的最大对称半径，并记录目前右端点最大的回文子串，枚举对称中心，如果当前对称中心在记录的回文子串内，就可以用对称过去的那个点来更新当前这个点，但是要注意如果对称过去那个点的半径对称过来超出了右端点，我们要截断这部分。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=3e7+5;
int d[N];

int manacher(int n,string s){
    int res=-1;
    string a="!";
    for(int i=0;i<n;i++) a+="#",a+=s[i];
    a+="#$";
    n=(n<<1)+1;
    d[1]=1;
    for(int i=2,l=1,r=1;i<=n;i++){
        if(i<=r) d[i]=min(d[l+r-i],1+r-i);
        while(a[i-d[i]]==a[i+d[i]]) d[i]++;
        if(i+d[i]-1>r) r=i+d[i]-1,l=i-d[i]+1;
    }
    for(int i=1;i<=n;i++) res=max(res,d[i]-1);
    return res;
}

int main(){
    string s;
    cin>>s;
    int n=s.size();
    cout<<manacher(n,s);
    return 0;
}

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

虽然叫扩展 KMP，但是这个算法却和 Manacher 有异曲同工之妙。

算法的核心在于求出 $Z$ 函数，而 $Z(i)$ 表示 $s[0,n-1]$ 与 $s[i,n-1]$ 的最长公共前缀。

考虑维护目前所有 $Z$ 函数前缀区间中右端点最大的那一个区间的左右端点 $l,r$，并枚举 $i$，考虑如下几种情况：

  1. 若 $i\le r$，由 $Z$ 函数的性质（$s[0,l-r]=s[l,r]$）可以知道：$s[i,r]=s[i-l,r-l]$。那就有 $Z(i)\ge \min(Z(i-l),r-i+1)$。（注：这里与 $r-l+1$ 取最小值的目的和马拉车算法中一样，对右端点以外的我们并不清楚，所以需要重新计算。）此时又需要分类讨论：
    - 若 $Z(i-l) < r-l+1$，说明继承过来的函数值连右端点都没到，不可能能继续扩展，直接赋值即可。
    - 若 $Z(i-l) \ge r-l+1$ 说明继承过来的函数值顶到了最优右端点，可以继续向右扩展，直接暴力即可。
  2. 若 $i > r$，同样暴力即可。

做完以上操作后，更新最 $l,r$ 即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=3e7+5;
int d[N];

int manacher(int n,string s){
    int res=-1;
    string a="!";
    for(int i=0;i<n;i++) a+="#",a+=s[i];
    a+="#$";
    n=(n<<1)+1;
    d[1]=1;
    for(int i=2,l=1,r=1;i<=n;i++){
        if(i<=r) d[i]=min(d[l+r-i],1+r-i);
        while(a[i-d[i]]==a[i+d[i]]) d[i]++;
        if(i+d[i]-1>r) r=i+d[i]-1,l=i-d[i]+1;
    }
    for(int i=1;i<=n;i++) res=max(res,d[i]-1);
    return res;
}

int main(){
    string s;
    cin>>s;
    int n=s.size();
    cout<<manacher(n,s);
    return 0;
}