记录编号	371526	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2016]找相同子串	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	2.527 s
提交时间	2017-02-16 11:30:31	内存使用	14.79 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=200005<<1;
char s1[maxn],s2[maxn];int r[maxn],len1,len2,N,K;
int height[maxn],sa[maxn],Rank[maxn],wa[maxn],wb[maxn],cnt[maxn];
int A[maxn],H[maxn];
inline bool R_cmp(int *y,int a,int b,int len){
	return y[a]==y[b]&&y[a+len]==y[b+len];
}
inline void Rabit_sa(int n,int m){
	int *t,*x=wa,*y=wb,i,j,p;
	for(i=0;i<m;i++)cnt[i]=0;
	for(i=0;i<n;i++)cnt[x[i]=r[i]]++;
	for(i=1;i<m;i++)cnt[i]+=cnt[i-1];
	for(i=n-1;~i;i--)sa[--cnt[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,m=p){
		for(p=0,i=n-j;i<n;i++)y[p++]=i;
		for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
		for(i=0;i<m;i++)cnt[i]=0;
		for(i=0;i<n;i++)cnt[x[y[i]]]++;
		for(i=1;i<m;i++)cnt[i]+=cnt[i-1];
		for(i=n-1;~i;i--)sa[--cnt[x[y[i]]]]=y[i];
		for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
			x[sa[i]]=R_cmp(y,sa[i],sa[i-1],j)?p-1:p++;
	}
}
inline void Rabit_H(int n){
	int i,j,k=0;
	for(i=0;i<=n;i++)Rank[sa[i]]=i;
	for(i=0;i<n;height[Rank[i++]]=k)
	for(k?k--:k,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);
}
inline LL Rabit_ans(bool b){
	int i,j;LL cntA,totB=0,res=0,cot=0;
	for(i=1;i<=N;i++)
		if(height[i]<K)totB=cot=0;
		else{
			cntA=0;
			if((sa[i-1]<len1)^b)totB+=height[i]-K+1,cntA++;
			while(cot&&height[i]<=H[cot])
				cntA+=A[cot],totB-=(H[cot]-height[i])*1ll*A[cot],cot--;
			A[++cot]=cntA,H[cot]=height[i];
			if((sa[i]>len1)^b)res+=totB;
		}
	return res;
}
int main(){
	freopen("find_2016.in","r",stdin);freopen("find_2016.out","w",stdout);
	scanf("%s%s",s1,s2);K=1;
	len1=strlen(s1),len2=strlen(s2),N=len1+len2+1;
	for(int i=0;i<len1;i++)r[i]=s1[i];r[len1]=1;
	for(int i=0;i<len2;i++)r[i+len1+1]=s2[i];r[N]=0;
	Rabit_sa(N+1,200),Rabit_H(N);
	printf("%lld\n",Rabit_ans(0)+Rabit_ans(1));
}