记录编号	274779	评测结果	AAAAAAAAAA
题目名称	[POJ3415]公共子串	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	4.541 s
提交时间	2016-06-29 18:51:06	内存使用	15.71 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=400010;
char s[N];
int k,n,i,j,len;

int Ws[N],Wv[N],Wa[N],Wb[N],r[N],sa[N],h[N];
bool cmp(int *r,int l,int x,int y){
	return r[x]==r[y]&&r[x+l]==r[y+l];
}
void da(){
	int i,j,p=0,m=30,*x=Wa,*y=Wb;
	for (i=0;i<=m;i++) Ws[i]=0;
	for (i=1;i<=n;i++) Ws[x[i]=s[i]]++;
	for (i=1;i<=m;i++) Ws[i]+=Ws[i-1];
	for (i=n;i>0;i--) sa[Ws[x[i]]--]=i;
	for (j=1;p<n;j*=2,m=p){
		for (i=n-j+1,p=0;i<=n;i++) y[++p]=i;
		for (i=1;i<=n;i++)
			if (sa[i]>j) y[++p]=sa[i]-j;
		for (i=1;i<=n;i++) Wv[i]=x[y[i]];
		for (i=0;i<=m;i++) Ws[i]=0;
		for (i=1;i<=n;i++) Ws[Wv[i]]++;
		for (i=1;i<=m;i++) Ws[i]+=Ws[i-1];
		for (i=n;i>0;i--) sa[Ws[Wv[i]]--]=y[i];
		swap(x,y);
		for (p=x[sa[1]]=1,i=2;i<=n;i++) x[sa[i]]=(cmp(y,j,sa[i],sa[i-1])?p:++p);
	}
}
int fa[N],size[2][N],a[N];
void geth(){
	int i,j,k;
	for (i=1;i<=n;i++) r[sa[i]]=i,fa[i]=a[i]=i,size[sa[i]>len][i]=1;
	for (k=h[r[0]]=0,i=1;i<=n;h[r[i++]]=k)
		for (k=max(h[r[i-1]]-1,0),j=sa[r[i]-1];s[i+k]==s[j+k];k++);
}
bool cmp1(const int x,const int y){
	return h[x]>h[y];
}
long long ans;
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void Merge(int x){
	int a=find(x),b=find(x-1);
	ans+=(size[0][a]*size[1][b]+size[1][a]*size[0][b])*(h[x]-k+1);
	fa[b]=a;
	size[0][a]+=size[0][b];
	size[1][a]+=size[1][b];
}

int main()
{
	freopen("commonsubstrings.in","r",stdin);
	freopen("commonsubstrings.out","w",stdout);
	do{
		scanf("%d",&k);
		if (k==0) return 0;
		scanf("%s",s+1);
		len=strlen(s+1);
		s[len+1]=96;
		scanf("%s",s+len+2);
		n=strlen(s+1);
		for (i=1;i<=n;i++) s[i]-=95;
		memset(size,0,sizeof size);
		da();geth();
		sort(a+1,a+n+1,cmp1);
		ans=0;
		for (i=1;i<=n;i++)
			if (h[a[i]]>=k) Merge(a[i]);
		printf("%lld\n",ans);
	}while (1);
}