ooliver

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

ooliver OI

前言

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

题单

CF1200E Compress Words

字符串哈希题。

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

代码：

C++

#include
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>T;
    for(int i=1;i>s;
        m=s.size(),s="#"+s;
        solve();
    }
    for(int i=1;i

`#include
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;iN;i++) mi[i]=mi[i-1]*p;
}
 
void solve(){
    int ans=0;
    for(int i=1;im;i++) b[i]=(b[i-1]*p+s[i])%mod;
    for(int i=1;imin(n,m);i++){
        if(a[n]-a[n-i]*mi[i]==b[i]){
            ans=i;
        }
    }
    for(int i=ans+1;im;i++){
        a[n+1]=(a[n]*p+s[i])%mod;
        now+=s[i],n++;
    }
}
 
signed main(){
    init();
    cin>>T;
    for(int i=1;iT;i++){
        cin>>s;
        m=s.size(),s="#"+s;
        solve();
    }
    for(int i=1;in;i++) coutnow[i];
    return 0;
}`

P8306 【模板】字典树 / Trie

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

代码：

C++

#include
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='A'&&c>n>>q;
    while(n--){
        cin>>s;
        trie.insert(s);
    }
    while(q--){
        cin>>s;
        cout>T;
    while(T--) solve();
    return 0;
}

`#include
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;iidx;i++) {
            memset(trie[i],0,sizeof trie[i]);
            tag[i]=0;
        }
        idx=0;
    }
    void insert(string s){
        int p=0;
        for(int i=0;is.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;is.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;
        couttrie.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
using namespace std;

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

void getpi(){
    for(int i=1;i0&&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

`#include
using namespace std;

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

void getpi(){
    for(int i=1;ia.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;in+m;i++) if(pi[i]==n) couti-2*n+1"\n";
    for(int i=0;in;i++) coutpi[i]" ";
    return 0;
}`

P13270 【模板】最小表示法

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

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

C++

#include
using namespace std;

int zxbsf(int n,string s){
    int i=0,j=1,k=0;//维护 i,j 两个指针以及当前匹配长度 k
    while(is[(j+k)%n]) i+=k+1,k=0;//如果 j 指针更优，则把 i 移到失配位置的后一位，保证最优解
        else if(s[(i+k)%n]>n>>s;
    int id=zxbsf(n,s);
    for(int i=0;i

`#include
using namespace std;

int zxbsf(int n,string s){
    int i=0,j=1,k=0;//维护 i,j 两个指针以及当前匹配长度 k
    while(in&&jn&&kn){//保证不越界
        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;in;i++) couts[(i+id)%n];
    return 0;
}`

P3805 【模板】Manacher

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

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

代码：

C++

#include
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;ir) r=i+d[i]-1,l=i-d[i]+1;
    }
    for(int i=1;i>s;
    int n=s.size();
    cout

`#include
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;in;i++) a+="#",a+=s[i];
    a+="#$";
    n=(n1)+1;
    d[1]=1;
    for(int i=2,l=1,r=1;in;i++){
        if(ir) 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;in;i++) res=max(res,d[i]-1);
    return res;
}

int main(){
    string s;
    cin>>s;
    int n=s.size();
    coutmanacher(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，考虑如下几种情况：

  • 若 i[PARSE ERROR: Undefined("Command(\"le\")")]r，由 Z 函数的性质（s[0,l-r]=s[l,r]）可以知道：s[i,r]=s[i-l,r-l]。那就有 Z(i)[PARSE ERROR: Undefined("Command(\"ge\")")]min(Z(i-l),r-i+1)。（注：这里与 r-l+1 取最小值的目的和马拉车算法中一样，对右端点以外的我们并不清楚，所以需要重新计算。）此时又需要分类讨论： - 若 Z(i-l)r，同样暴力即可。

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

代码：

C++

#include
using namespace std;

using ll=long long;
const int N=4e7+5;
int z[N];

void getz(int n,string s){
    for(int i=1,l=0,r=0;ir) r=i+z[i]-1,l=i;
    }
}

int main(){
    int n,m;
    ll ans1=0,ans2=0;
    string a,b;
    cin>>b>>a;
    n=a.size(),m=b.size();
    a=a+"#"+b;
    getz(n+m+1,a);
    for(int i=0;in) ans2^=(ll)(i-n)*(ll)(z[i]+1);
    }
    cout

`#include
using namespace std;

using ll=long long;
const int N=4e7+5;
int z[N];

void getz(int n,string s){
    for(int i=1,l=0,r=0;in;i++){
        if(ir&&z[i-l]r-i+1) z[i]=z[i-l];
        else{
            z[i]=max(r-i+1,0);
            while(z[i]+in&&s[z[i]+i]==s[z[i]]) z[i]++;
        }
        if(i+z[i]-1>r) r=i+z[i]-1,l=i;
    }
}

int main(){
    int n,m;
    ll ans1=0,ans2=0;
    string a,b;
    cin>>b>>a;
    n=a.size(),m=b.size();
    a=a+"#"+b;
    getz(n+m+1,a);
    for(int i=0;in+m;i++){
        if(i==0) ans1^=(ll)(n+1);
        else if(in) ans1^=(ll)(i+1)*(ll)(z[i]+1);
        else if(i>n) ans2^=(ll)(i-n)*(ll)(z[i]+1);
    }
    coutans1"\n"ans2;
    return 0;
}`

P2375 [NOI2014] 动物园

这个昨天写了一版很详细的，但是忘记保存了，懒得写详细了。。。

考虑枚举所有对 sumj 产生贡献的后缀 s[i,j] 的 i，不难发现求出 Z 函数后，i 作为左端点所能产生贡献的右端点的区间就可以表示了，差分即可。

代码：

C++

#include
using namespace std;

using ll=long long;
const int N=4e7+5;
const int mod=1e9+7;

vector getz(int n,string s){
    vector z(n,0);
    for(int i=1,l=0,r=0;ir) r=i+z[i]-1,l=i;
    }
    return z;
}

int main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        ll ans=1;
        string s;
        cin>>s;
        n=s.size();
        vector sum(n,0),z=getz(n,s);
        for(int i=0;i

`#include
using namespace std;

using ll=long long;
const int N=4e7+5;
const int mod=1e9+7;

vectorint> getz(int n,string s){
    vectorint> z(n,0);
    for(int i=1,l=0,r=0;in;i++){
        if(ir&&z[i-l]r-i+1) z[i]=z[i-l];
        else{
            z[i]=max(r-i+1,0);
            while(z[i]+in&&s[z[i]+i]==s[z[i]]) z[i]++;
        }
        if(i+z[i]-1>r) r=i+z[i]-1,l=i;
    }
    return z;
}

int main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        ll ans=1;
        string s;
        cin>>s;
        n=s.size();
        vectorint> sum(n,0),z=getz(n,s);
        for(int i=0;in;i++){
            int len=min(z[i],i);
            sum[i]++;
            if(i+lenn) sum[i+len]--;
        }
        for(int i=0;in;i++){
            if(i) sum[i]+=sum[i-1];
            ans=(ans*(sum[i]+1))%mod;
        }
        coutans"\n";
    }
    return 0;
}`