记录编号	254013	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2016]找相同子串	最终得分	100
用户昵称	dydxh	是否通过	通过
代码语言	C++	运行时间	2.316 s
提交时间	2016-04-24 13:34:44	内存使用	98.88 MiB

/*
Problem:Pmb;
Language:c++;
by dydxh;
Date:2016.04.23;
*/
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<utility>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<ctime>
#define ll long long
using namespace std;
const int oo=2000000000;
const int maxn=400001;
char S[2][maxn];
int L[2];
int Root;
ll Ans;
struct Suffix_Automaton{
	int Last,Cnt;
	int Tor[maxn<<1][27],Val[maxn<<1],Par[maxn<<1];
	void Initialize(){Last=Cnt=Root=1;}
	void Expand(int x){
		if(Tor[Last][x] && Val[Tor[Last][x]]==Val[Last]+1){
			Last=Tor[Last][x];
			return ;
		}
		int np=++Cnt;
		if(Tor[Last][x]){
			int p=Last,q=Tor[Last][x];Val[np]=Val[p]+1;
			memcpy(Tor[np],Tor[q],sizeof(Tor[np]));
			Par[np]=Par[q],Par[q]=np;
			while(p && Tor[p][x]==q) Tor[p][x]=np,p=Par[p];
		}
		else{
			int p=Last;Val[np]=Val[p]+1;
			while(p && Tor[p][x]==0) Tor[p][x]=np,p=Par[p];
			if(p==0) Par[np]=1;
			else{
				int q=Tor[p][x];
				if(Val[q]==Val[p]+1) Par[np]=q;
				else{
					int nq=++Cnt;Val[nq]=Val[p]+1;
					memcpy(Tor[nq],Tor[q],sizeof(Tor[nq]));
					Par[nq]=Par[q],Par[q]=Par[np]=nq;
					while(p && Tor[p][x]==q) Tor[p][x]=nq,p=Par[p];
				}
			}
		}
		Last=np;
	}
	void Build(int Th){
		if(Th==1) Last=1;
		for(int i=1;i<=L[Th];i++)
			Expand(S[Th][i]-'a'+1);
	}
	int Color[maxn<<1];
	bool Vis[maxn<<1];
	void Col(int x){
		while(x){
			if(Vis[x]) break;
			Vis[x]=true;Color[x]++;
			x=Par[x];
		}
	}
	int Siz[2][maxn<<1],Q[maxn<<1],Ser[maxn];
	void Sorter(){
		int Limit=max(L[0],L[1]);
		for(int i=1;i<=Cnt;i++) Ser[Val[i]]++;
		for(int i=1;i<=Limit;i++) Ser[i]+=Ser[i-1];
		for(int i=1;i<=Cnt;i++) Q[Ser[Val[i]]--]=i;
		for(int i=Cnt;i>=1;i--) Siz[0][Par[Q[i]]]+=Siz[0][Q[i]],Siz[1][Par[Q[i]]]+=Siz[1][Q[i]];
	}
	void Counter(){
		for(int i=1;i<=Cnt;i++){
			if(Color[i]<2) continue;
			Ans+=1LL*(Val[i]-Val[Par[i]])*Siz[0][i]*Siz[1][i];
		}
	}
}Sam;
inline int read(){
	int x=0;bool flag=false;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-') flag=true;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return flag?-x:x;
}
namespace Tsk1{
	int n,m,Li;
	char SS[505],T[505],Now[505];
	int Pre[505];
	void Judge(){
		memset(Pre,0,sizeof(Pre));
		int j=0;
		for(int i=2;i<=Li;i++){
			while(j && Now[i]!=Now[j+1]) j=Pre[j];
			if(Now[i]==Now[j+1]) j++;
		}
		j=0;
		for(int i=1;i<=m;i++){
			while(j && T[i]!=Now[j+1]) j=Pre[j];
			if(T[i]==Now[j+1]){
				j++;
				if(j==Li){
					Ans++;
					j=Pre[j];
				}
			}
		}
	}
	void Solve(){
		memcpy(SS,S[0],sizeof(SS));
		memcpy(T,S[1],sizeof(T));
		n=L[0],m=L[1];
		for(int i=1;i<=n;i++){
			Li=0;
			for(int j=i;j<=n;j++){
				Now[++Li]=SS[j];
				Judge();
			}
		}
		cout<<Ans<<endl;
	}
}
int main(){
	freopen("find_2016.in","r",stdin);
	freopen("find_2016.out","w",stdout);
	scanf("%s\n%s\n",S[0]+1,S[1]+1);
	L[0]=strlen(S[0]+1),L[1]=strlen(S[1]+1);
	/*if(L[0]<=500 && L[1]<=500){
		Tsk1::Solve();
		//Solve();
		return 0;
	}*/
	Sam.Initialize();
	Sam.Build(0);
	Sam.Build(1);
	int Now=Root;
	for(int i=1;i<=L[0];i++){
		int x=S[0][i]-'a'+1;
		Now=Sam.Tor[Now][x];
		Sam.Siz[0][Now]++;
		Sam.Col(Now);
	}
	memset(Sam.Vis,false,sizeof(Sam.Vis));
	Now=Root;
	for(int i=1;i<=L[1];i++){
		int x=S[1][i]-'a'+1;
		Now=Sam.Tor[Now][x];
		Sam.Siz[1][Now]++;
		Sam.Col(Now);
	}
	Sam.Sorter();
	Sam.Counter();
	cout<<Ans<<endl;
	//cout<<"Time has passed:"<<1.0*clock()/1000<<"s!"<<endl;
	return 0;
}