自动搬运

查看原文

来自洛谷，原作者为

	panyf **

搬运于2025-08-24 22:24:03，当前版本为作者最后更新于2021-08-21 09:42:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

考虑贪心地每次匹配两个 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;
}