记录编号	122886	评测结果	AAAAAAAAAA
题目名称	[POJ3415]公共子串	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	11.584 s
提交时间	2014-09-24 21:04:39	内存使用	7.76 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int SIZEN=200010;
int sum[SIZEN];
void basesort(int a[],int b[],int c[],int n,int m){
	memset(sum,0,sizeof(sum));
	for(int i=0;i<n;i++) sum[c[a[i]]]++;
	for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
	for(int i=n-1;i>=0;i--) b[--sum[c[a[i]]]]=a[i];
}
int A[SIZEN],B[SIZEN];
int x[SIZEN],y[SIZEN];
void sort_suf(char S[],int rank[],int sa[],int N){
	for(int i=0;i<N;i++) x[i]=S[i],A[i]=i;
	basesort(A,sa,x,N,256);
	rank[sa[0]]=1;
	for(int i=1;i<N;i++)
		if(x[sa[i]]==x[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]];
		else rank[sa[i]]=rank[sa[i-1]]+1;
	for(int k=1;k<=N;k<<=1){
		for(int i=0;i<N;i++){
			A[i]=i;
			x[i]=rank[i];
			y[i]=i+k<N?rank[i+k]:0;
		}
		basesort(A,B,y,N,N);
		basesort(B,sa,x,N,N);
		rank[sa[0]]=1;
		for(int i=1;i<N;i++)
			if(x[sa[i]]==x[sa[i-1]]&&y[sa[i]]==y[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]];
			else rank[sa[i]]=rank[sa[i-1]]+1;
	}
	for(int i=0;i<N;i++) rank[sa[i]]=i;
}
void calc_height(char S[],int rank[],int sa[],int height[],int N){
	int h=0;
	for(int i=0;i<N;i++){
		if(rank[i]==0) h=0;
		else{
			int k=sa[rank[i]-1];
			if(--h<0) h=0;
			while(S[i+h]==S[k+h]) h++;
		}
		height[rank[i]]=h;
	}
}
int K;
int n,m;
char S1[SIZEN],S2[SIZEN];
int N;
char S[SIZEN];
int rank[SIZEN],sa[SIZEN],height[SIZEN];
int H[SIZEN];
int top;
int flag(int x){
	if(x<n) return 0;
	if(x>n) return 1;
	return -1;
}
void work(void){
	LL ans=0;
	LL cnt[2]={0};
	//A,B借来一用......
	top=cnt[0]=cnt[1]=0;
	for(int i=1;i<N;i++){
		if(height[i]<K) top=cnt[0]=cnt[1]=0;
		else{
			A[0]=B[0]=0;
			while(top>0&&H[top]>=height[i]){
				A[0]+=A[top],B[0]+=B[top];
				cnt[0]-=(LL)A[top]*(LL)(H[top]-K+1),cnt[1]-=(LL)B[top]*(LL)(H[top]-K+1);
				top--;
			}
			top++;
			H[top]=height[i];
			A[top]=A[0];B[top]=B[0];
			flag(sa[i-1])?B[top]++:A[top]++;
			cnt[0]+=(LL)A[top]*(LL)(H[top]-K+1);cnt[1]+=(LL)B[top]*(LL)(H[top]-K+1);
			flag(sa[i])?ans+=cnt[0]:ans+=cnt[1];
		}
	}
	//printf("%I64d\n",ans);
	printf("%lld\n",ans);
}
void prepare(void){
	sort_suf(S,rank,sa,N);
	calc_height(S,rank,sa,height,N);
}
bool read(void){
	scanf("%d",&K);
	if(!K) return false;
	scanf("%s",S1);
	scanf("%s",S2);
	n=strlen(S1),m=strlen(S2);
	strcpy(S,S1);
	S[n]='#';
	strcpy(S+n+1,S2);
	N=n+m+1;
	return true;
}
int main(){
	freopen("commonsubstrings.in","r",stdin);
	freopen("commonsubstrings.out","w",stdout);
	while(read()){
		prepare();
		work();
	}
	return 0;
}