记录编号	409419	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2016]找相同子串	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	0.589 s
提交时间	2017-05-27 19:07:35	内存使用	36.79 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 200010
using namespace std;
char str[MAXN<<1];
int len[MAXN<<1],fa[MAXN<<1],trans[MAXN<<1][26],right[MAXN<<1],last,cnt,rt,n;
void Extend(int x){
	int p=last,np=last=++cnt;
	len[np]=len[p]+1;right[np]=1;
	while(p&&!trans[p][x])trans[p][x]=np,p=fa[p];
	if(!p)fa[np]=rt;
	else{
		int q=trans[p][x];
		if(len[p]+1==len[q])fa[np]=q;
		else{
			int nq=++cnt;
			len[nq]=len[p]+1;
			copy(trans[q],trans[q]+26,trans[nq]);
			fa[nq]=fa[q];
			fa[q]=fa[np]=nq;
			while(p&&trans[p][x]==q)trans[p][x]=nq,p=fa[p];}}}
int c[MAXN<<1]={0},a[MAXN<<1]={0},appear[MAXN<<1]={0};
void RadixSort(){
	for(int i=0;i<=n;i++)c[i]=0;
	for(int i=1;i<=cnt;i++)c[len[i]]++;
	for(int i=1;i<=n;i++)c[i]+=c[i-1];
	for(int i=cnt;i>=1;i--)a[c[len[i]]--]=i;}
long long ans=0,f[MAXN<<1]={0};
int sb(){
	freopen("find_2016.in","r",stdin);
	freopen("find_2016.out","w",stdout);
	scanf("%s",str+1);
	n=strlen(str+1);
	last=cnt=rt=1;
	for(int i=1;i<=n;i++)Extend(str[i]-'a');
	RadixSort();
	int u;
	for(int i=cnt;i>=1;i--)u=a[i],right[fa[u]]+=right[u];
	int le=0;u=rt;
	scanf("%s",str+1);n=strlen(str+1);
	for(int i=1;i<=n;i++){
		int c=str[i]-'a';
		if(trans[u][c])le++,u=trans[u][c];
		else{
			while(u&&!trans[u][c])u=fa[u];
			if(!u)u=rt;
			else le=len[u]+1,u=trans[u][c];}
		appear[u]++,ans+=(long long)right[u]*(le-len[fa[u]]);}
	for(int i=cnt;i>=1;i--)u=a[i],f[fa[u]]+=f[u]+appear[u];
	for(int i=2;i<=cnt;i++)ans+=(long long)right[i]*f[i]*(len[i]-len[fa[i]]);
	printf("%lld",ans);
	return 0;}
int chh=sb();
int main(){;}