【BZOJ4566】找相同字符（后缀数组）

题面

BZOJ

题解

后缀数组的做法，应该不是很难想

首先看到两个不同的串，当然是接在一起求\(SA,height\)

那么，考虑一下暴力

在两个串各枚举一个后缀，他们的\(lcp\)就是对答案产生的贡献

现在优化一下，按照\(SA\)的顺序枚举来处理\(lcp\)

利用一个单调栈维护一下，每次记录一下前面有多少个的贡献和当前答案一样就好啦

只是有点难写。。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 440000

#define ll long long

int n,gr[MAX];

int SA[MAX],hg[MAX],rk[MAX];

int a[MAX],t[MAX],x[MAX],y[MAX];

bool cmp(int i,int j,int k){return y[i]==y[j]&&y[i+k]==y[j+k];}

void GetSA()

{

	int m=50;

	for(int i=1;i<=n;++i)t[x[i]=a[i]]++;

	for(int i=1;i<=m;++i)t[i]+=t[i-1];

	for(int i=n;i>=1;--i)SA[t[x[i]]--]=i;

	for(int k=1;k<=n;k<<=1)

	{

		int p=0;

		for(int i=1;i<=n;++i)y[i]=0;

		for(int i=n-k+1;i<=n;++i)y[++p]=i;

		for(int i=1;i<=n;++i)if(SA[i]>k)y[++p]=SA[i]-k;

		for(int i=0;i<=m;++i)t[i]=0;

		for(int i=1;i<=n;++i)t[x[y[i]]]++;

		for(int i=1;i<=m;++i)t[i]+=t[i-1];

		for(int i=n;i>=1;--i)SA[t[x[y[i]]]--]=y[i];

		swap(x,y);

		x[SA[1]]=p=1;

		for(int i=2;i<=n;++i)x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;

		if(p>=n)break;

		m=p;

	}

	for(int i=1;i<=n;++i)rk[SA[i]]=i;

	for(int i=1,j=0;i<=n;++i)

	{

		if(j)--j;

		while(a[i+j]==a[SA[rk[i]-1]+j])++j;

		hg[rk[i]]=j;

	}

}

int Q1[MAX],top1,S1[MAX];

int Q2[MAX],top2,S2[MAX];

ll ans,sum1,sum2;

char ch[MAX];

int main()

{

	scanf("%s",ch+1);

	for(int i=1,l=strlen(ch+1);i<=l;++i)a[++n]=ch[i]-96,gr[n]=1;

	a[++n]=27;

	scanf("%s",ch+1);

	for(int i=1,l=strlen(ch+1);i<=l;++i)a[++n]=ch[i]-96,gr[n]=2;

	GetSA();

	for(int i=1,tot=0;i<n;++i)

	{

		ans+=(gr[SA[i]]==1)?sum2:sum1;

		ll tmp1=0;

		while(top1&&Q1[top1]>=hg[i+1])

		{

			tmp1+=S1[top1];

			sum1-=1ll*(Q1[top1]-hg[i+1])*S1[top1];

			--top1;

		}

		++top1;S1[top1]=tmp1;Q1[top1]=hg[i+1];

		ll tmp2=0;

		while(top2&&Q2[top2]>=hg[i+1])

		{

			tmp2+=S2[top2];

			sum2-=1ll*(Q2[top2]-hg[i+1])*S2[top2];

			--top2;

		}

		++top2;S2[top2]=tmp2;Q2[top2]=hg[i+1];

		if(gr[SA[i]]==1)++S1[top1],sum1+=hg[i+1];

		else ++S2[top2],sum2+=hg[i+1];

	}

	printf("%lld\n",ans);

	return 0;

}