记录编号	265224	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2016]找相同子串	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.277 s
提交时间	2016-06-01 22:02:52	内存使用	20.53 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define ll long long

const int N=400010;
char s[N];
int i,j,ls,n,sa[N],r[N],h[N],wa[N],wb[N],Ws[N],wv[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,p=0,l,m=99,*x=wa,*y=wb;
	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 (l=1;p<n;l*=2,m=p){
		for (p=0,i=n-l+1;i<=n;i++) y[++p]=i;
		for (i=1;i<=n;i++)
			if (sa[i]>l) y[++p]=sa[i]-l;
		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,l,sa[i],sa[i-1])?p:++p);
	}
}
void geth(){
	int i,k;
	for (i=1;i<=n;i++) r[sa[i]]=i;
	for (h[r[0]]=k=0,i=1;i<=n;h[r[i++]]=k)
		for (k=max(h[r[i-1]]-1,0),j=sa[r[i]-1];s[j+k]==s[i+k];k++);
}

int fa[N],a[N];
ll ns[N],nt[N],ans;
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool cmp1(const int x,const int y){
	return h[x]>h[y];
}
void merge(int x){
	if (x==1) return;
	int a=find(x),b=find(x-1);
	ans+=(ns[a]*nt[b]+nt[a]*ns[b])*h[x];
	ns[a]+=ns[b];nt[a]+=nt[b];
	fa[b]=a;
}

int main()
{
	freopen("find_2016.in","r",stdin);
	freopen("find_2016.out","w",stdout);
	scanf("%s",s+1);
	ls=strlen(s+1);
	s[ls+1]=96;
	scanf("%s",s+ls+2);
	n=strlen(s+1);
	for (i=1;i<=n;i++) s[i]-=95;
	da();geth();
	for (i=1;i<=n;i++){
		a[i]=fa[i]=i;
		ns[i]=(sa[i]<=ls);
		nt[i]=1-ns[i];
	}
	
	sort(a+1,a+n+1,cmp1);
	for (i=1;i<=n;i++) merge(a[i]);
	cout<<ans<<endl;
	return 0;
}