这题的处理方法比较经典，
先把两个串拼接起来，之后利用后缀数组进行扫描。

这里要抓的精髓是：
1.如果有m个串和串x的最长公共前缀长度为n，那么
就产生m*(n-k+1)对匹配的串。
2.用一个栈（单调数组）维护已扫描的各个串和当前扫描的串的最长公共前缀长度。

需要注意的是：
1.拼接串的时候要加入分隔符。
2.只统计长度≥K的公共串

代码示例：
void DoubleAlgorithm(char *a,int n){
	int *tmp;
	SA=mem[3];Rank=mem[4];cnt=mem[0];tSA=mem[1];tRank=mem[2];
	for (int i=0;i<256;i++)cnt[i]=0;
	for (int i=0;i<n;i++)cnt[a[i]]++;
	for (int i=1;i<256;i++)cnt[i]+=cnt[i-1];
	for (int i=n-1;i>=0;i--)SA[--cnt[a[i]]]=i;
	Rank[SA[0]]=0;for (int i=1;i<n;i++)
		Rank[SA[i]]=Rank[SA[i-1]]+(a[SA[i]]!=a[SA[i-1]]);
	for (int l=1;l<n && Rank[SA[n-1]]!=n-1;l<<=1){
		for (int i=0;i<n;i++)cnt[Rank[SA[i]]]=i+1;
		for (int i=n-1;i>=0;i--)if (SA[i]>=l)
			tSA[--cnt[Rank[SA[i]-l]]]=SA[i]-l;
		for (int i=n-1;i>=0;i--)if (SA[i]+l>=n)
			tSA[--cnt[Rank[SA[i]]]]=SA[i];
		tRank[tSA[0]]=0;for (int i=1;i<n;i++)
			tRank[tSA[i]]=tRank[tSA[i-1]]+(
				Rank[tSA[i]]!=Rank[tSA[i-1]] ||
				Rank[tSA[i]+l]!=Rank[tSA[i-1]+l]);
		tmp=SA;SA=tSA;tSA=tmp;
		tmp=Rank;Rank=tRank;tRank=tmp;
	}
	int j;
	for (int i=0;i<n;i++){
		if (!Rank[i])Height[Rank[i]]=0;
		else{
			if (i && Height[Rank[i-1]]>1)j=Height[Rank[i-1]]-1;else j=0;
			for (;a[i+j]==a[SA[Rank[i]-1]+j];j++);
			Height[Rank[i]]=j;
		}
	}
}
int COUNT(int a){
	if (a<K)return 0;
	return a-K+1;
}

                scanf("%s",A);
		for (nA=0;A[nA];nA++);
		scanf("%s",A+nA+1);
		for (nB=0;A[nA+1+nB];nB++);
		N=nA+nB+1;
		A[nA]=1;A[N]=2;
		DoubleAlgorithm(A,N);
		ca=cnt;cb=tSA;
		ca[0]=cb[0]=0;
		for (int i=0;i<N;i++){
			ca[i+1]=(i?ca[i]:0);cb[i+1]=(i?cb[i]:0);
			if (SA[i]<nA)ca[i+1]++;
			else if (SA[i]>nA)cb[i+1]++;
		}
		ret=0;top=0;sa=sb=0;
		for (int i=0;i<N;i++){
			if (!i)continue;
			stA[top]=i-1;stB[top]=Height[i];top++;
			if (SA[i-1]<nA)sb+=COUNT(Height[i]);
			else if (SA[i-1]>nA)sa+=COUNT(Height[i]);
			while (top>1 && stB[top-2]>=stB[top-1]){
				if (stB[top-2]>stB[top-1]){
					sb-=(long long)(ca[stA[top-1]]-ca[stA[top-2]])*
						(long long)(COUNT(stB[top-2])-COUNT(stB[top-1]));
					sa-=(long long)(cb[stA[top-1]]-cb[stA[top-2]])*
						(long long)(COUNT(stB[top-2])-COUNT(stB[top-1]));
					stB[top-2]=stB[top-1];
				}
				top--;
			}
			if (SA[i]<nA)ret+=sa;
			else if (SA[i]>nA)ret+=sb;
		}
		printf("%I64d\n",ret);

• Re:雁过留声——后缀数组+扫描 (80) smallbox 2010-07-04 00:58:03