P6793 [SNOI2020] 字符串（后缀数组）

· · 题解

提供一个简单的后缀数组做法。

考虑贪心地每次匹配两个 lcp 最长的子串。

求出 height 数组，和P2178 [NOI2015] 品酒大会一样从大到小排序，用并查集维护即可。

只需要记录当前集合还未匹配的 a 串子串和 b 串子串数量。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+3;
char s[N];
int sa[N],u[N],v[N],h[N],t[N],f[N],id[N],p[N],q[N];
long long ans;
int gf(int x){return f[x]==x?x:f[x]=gf(f[x]);}
void mg(int x,int y,int w){
    p[y]+=p[x],q[y]+=q[x],f[x]=y;
    if(p[y]<q[y])return ans+=w*1ll*p[y],q[y]-=p[y],p[y]=0,void();
    ans+=w*1ll*q[y],p[y]-=q[y],q[y]=0;
}//合并两个集合，pq分别表示还未匹配的a串子串和b串子串数量
int main(){
    int*rk=u,*b=v,n,n2,o,m=131,i,j,k=0,x,y;
    scanf("%d%d",&n2,&o),scanf("%s",s+1),s[n2+1]='z'+1,scanf("%s",s+n2+2),n=n2*2+1;
    for(i=1;i<=n;++i)++t[s[i]];
    for(i=1;i<=m;++i)t[i]+=t[i-1];
    for(i=n;i;--i)sa[t[rk[i]=s[i]]--]=i;
    for(i=1;k<n;i*=2,m=k){
        for(j=n-i+1,k=0,memset(t,0,m*4+4);j<=n;++j)b[++k]=j;
        for(j=1;j<=n;++j)if(++t[rk[j]],sa[j]>i)b[++k]=sa[j]-i;
        for(j=1;j<=m;++j)t[j]+=t[j-1];
        for(j=n;j;--j)sa[t[rk[b[j]]]--]=b[j];
        for(j=1,swap(rk,b),k=y=0;j<=n;++j,y=x)x=sa[j],rk[x]=b[x]==b[y]&&b[x+i]==b[y+i]?k:++k;
    }
    for(i=1,k=0;i<=n;h[rk[i++]]=k)if(rk[i]>1)for(j=sa[rk[i]-1],k=max(0,k-1);s[i+k]==s[j+k];++k);//以上为后缀数组板子
    for(i=1;i<=n;++i)if(f[i]=id[i]=i,i<=n2-o+1)p[i]=1;else if(i>n2+1&&i<=n2*2-o+2)q[i]=1;
    sort(id+2,id+n,[](int x,int y){return h[x]>h[y];});
    for(i=2;i<n;++i)mg(gf(sa[id[i]]),gf(sa[id[i]-1]),max(0,o-h[id[i]]));
    cout<<ans;
    return 0;
}