POJ3415 Common Substrings 后缀数组+单调栈

思路:

最近好像是被<囚人的旋律>里的主人公的心情所影响,所以效率很低.

例如,这样一道傻逼题我居然傻逼了3个小时!

我整个人都单调栈了.

就是求个height,然后在连续块内,我们对于每个属于串A的后缀分别计算出在他前面的属于串B的后缀的影响,在计算出在他之后的属于B的后缀的影响.

然后我们从前到后,再从后到前扫描一边,利用一个单调栈维护一下属于串B的后缀即可.

说起来简单...不过写起来...一定是我太鶸了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

#define N 200010
char s1[N],s2[N],s[N];int v[N],tv[N],q[N],c[N],sa[N];
inline bool cmp(int x,int y,int hl,int n){
	return v[x]==v[y]&&((x+hl>=n&&y+hl>=n)||(x+hl<n&&y+hl<n&&v[x+hl]==v[y+hl]));
}
inline void calcsa(char*s,int n,int m,int*sa){
	register int i,j,k;int id,hl;
	for(i=0;i<m;++i)c[i]=0;
	for(i=0;i<n;++i)++c[v[i]=s[i]];
	for(i=1;i<m;++i)c[i]+=c[i-1];
	for(i=n-1;i>=0;--i)sa[--c[v[i]]]=i;
	for(int d=1;;++d){
		for(hl=1<<(d-1),id=0,i=n-hl;i<n;++i)q[id++]=i;
		for(i=0;i<n;++i)if(sa[i]>=hl)q[id++]=sa[i]-hl;
		for(i=0;i<m;++i)c[i]=0;
		for(i=0;i<n;++i)++c[v[q[i]]];
		for(i=1;i<m;++i)c[i]+=c[i-1];
		for(i=n-1;i>=0;--i)sa[--c[v[q[i]]]]=q[i];
		for(i=m=0;i<n;i=j+1,++m){
			for(j=i;j<n-1&&cmp(sa[j],sa[j+1],hl,n);++j);
			for(k=i;k<=j;++k)tv[sa[k]]=m;
		}for(i=0;i<n;++i)v[i]=tv[i];
		if(m==n)break;
	}
}
int rk[N],h[N];
inline void calch(char*s,int n,int*sa,int*rk,int*h){
	register int i,j;
	for(i=0;i<n;++i)rk[sa[i]]=i;
	for(i=0;i<n;++i)if(rk[i]){
		j=max(0,h[rk[i-1]]-1);while(i+j<n&&sa[rk[i]-1]+j<n&&s[i+j]==s[sa[rk[i]-1]+j])++j;h[rk[i]]=j;
	}
}

int lim;

struct Case{
	int v,c;
	Case(){}
	Case(int _v,int _c):v(_v),c(_c){}
}stk[N];
int top,nowcnt;long long sum[N];int cnt[N];

int belong[N];
int main(){
	int i,j,k;
	while(scanf("%d",&lim)&&lim){
		scanf("%s%s",s1,s2);int len1=strlen(s1),len2=strlen(s2);
		memset(s,0,sizeof s);int len=0;for(i=0;i<len1;++i)belong[len]=1,s[len++]=s1[i];s[len++]='$';for(i=0;i<len2;++i)belong[len]=2,s[len++]=s2[i];
		calcsa(s,len,256,sa),calch(s,len,sa,rk,h);

		LL ans=0;int tmp;
		for(i=1;i<len;){
			if(h[i]>=lim){
				for(j=i;j<len&&h[j]>=lim;++j);
				for(top=0,h[i-1]=h[i],tmp=h[j],h[j]=h[j-1],k=i-1;k<j;++k){
					nowcnt=0;
					while(top&&stk[top].v>=h[k])nowcnt+=stk[top--].c;
					if(nowcnt)stk[++top]=Case(h[k],nowcnt),sum[top]=sum[top-1]+(LL)stk[top].c*stk[top].v,cnt[top]=cnt[top-1]+stk[top].c;
					if(belong[sa[k]]==2)ans+=sum[top]-(LL)cnt[top]*(lim-1);
					else{
						nowcnt=1;while(top&&stk[top].v>=h[k+1])nowcnt+=stk[top--].c;
						stk[++top]=Case(h[k+1],nowcnt),sum[top]=sum[top-1]+(LL)stk[top].c*stk[top].v,cnt[top]=cnt[top-1]+stk[top].c;
					}
					
				}
				for(top=0,k=j-1;k>=i-1;--k){
					nowcnt=0;
					while(top&&stk[top].v>=h[k+1])nowcnt+=stk[top--].c;
					if(nowcnt)stk[++top]=Case(h[k+1],nowcnt),sum[top]=sum[top-1]+(LL)stk[top].c*stk[top].v,cnt[top]=cnt[top-1]+stk[top].c;
					if(belong[sa[k]]==2)ans+=sum[top]-(LL)cnt[top]*(lim-1);
					else{
						nowcnt=1;while(top&&stk[top].v>=h[k])nowcnt+=stk[top--].c;
						stk[++top]=Case(h[k],nowcnt),sum[top]=sum[top-1]+(LL)stk[top].c*stk[top].v,cnt[top]=cnt[top-1]+stk[top].c;
					}
				}h[j]=tmp;
				i=j;
			}else++i;
		}
		cout<<ans<<endl;
	}
	return 0;
}