Chrysanthemum's Blog

题意：给你两个字符串和k，求不小于k的公共子串的个数。

计算A的某个后缀与B的某个后缀的最长公共前缀L，如果L大于等于k，就加上L-k+1。

我们先把B复制到A后面，并加一个分隔符。

我们考虑同一组大于等于k的height，对于每个B计算之前每个A对其的贡献，对于每个A计算之前每个B对其的贡献。但这样是N²的。所以，我们利用lcp的性质，i~j所有height的最小值，所以我们只要维护一个单调递增的栈即可。

代码：

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int K,l,n,top;
ll sum,ans;
int wa[200100],wb[200100],ws[200100],wv[200100],sa[200100],rank[200100],r[200100],height[200100],f[200100],a[200100],b[200100];
char s[200100];
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
	int i,j,p,*x=wa,*y=wb,*t;
	for (i=0;i<m;i++) ws[i]=0;
	for (i=0;i<n;i++) ws[x[i]=r[i]]++;
	for (i=1;i<m;i++) ws[i]+=ws[i-1];
	for (i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
	for (j=1,p=1;p<n;j*=2,m=p)
	{
		p=0;
		for (i=n-j;i<n;i++) y[p++]=i;
		for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;
		for (i=0;i<n;i++) wv[i]=x[y[i]];
		for (i=0;i<m;i++) ws[i]=0;
		for (i=0;i<n;i++) ws[wv[i]]++;
		for (i=1;i<m;i++) ws[i]+=ws[i-1];
		for (i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
		for (t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
			x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void calheight(int *r,int *sa,int n)
{
	int i,j,k=0;
	for (i=1;i<=n;i++) rank[sa[i]]=i;
	for (i=0;i<n;height[rank[i++]]=k)
		for (k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
int main()
{
	while (1)
	{
		scanf("%d",&K);
		if (!K) break;
		scanf("%s",s);
		l=strlen(s);
		s[l]=1;;
		scanf("%s",s+l+1);
		n=strlen(s);
		for (int i=0;i<n;i++) r[i]=s[i];
		r[n]=0;
		da(r,sa,n+1,200);
		calheight(r,sa,n);
		for (int i=2;i<=n;i++)
		{
			f[i]=(sa[i]<l);
			height[i]-=K-1;
			if (height[i]<0) height[i]=0;
		}
		height[n+1]=0;
		a[0]=-1;ans=0;
		for (int id=0;id<=1;id++)
		{
			sum=0,top=0;
			for (int i=2;i<=n;i++)
			{
				if (f[i]!=id) ans+=sum;
				a[++top]=height[i+1];
				b[top]=(f[i]==id);
				sum+=(ll)a[top]*b[top];
				while (a[top-1]>=a[top])
				{
					sum-=(ll)(a[top-1]-a[top])*b[top-1];
					a[top-1]=a[top];
					b[top-1]+=b[top];
					top--;
				}
			}
		}
		printf("%lld\n",ans);
	}
}