记录编号	394612	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2016]找相同子串	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.270 s
提交时间	2017-04-13 19:41:28	内存使用	55.62 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 4e5+6;
int len[MAXN], next[MAXN][26], link[MAXN], size[MAXN];
const int root = 1;
int cnt = 1;
int last = 1;
void expand(int c){
	int cur = ++cnt; len[cur] = len[last]+1; size[cur] = 1;
	int p;
	for(p = last; p && !next[p][c]; p = link[p]){
		next[p][c] = cur;	
	}
	if(!p)link[cur] = 1;
	else{
		int q = next[p][c];
		if(len[q] == len[p]+1)link[cur] = q;
		else{
			int clone = ++cnt;
			link[clone] = link[q]; len[clone] = len[p]+1;
			memcpy(next[clone], next[q], sizeof next[0]);
			for(; p && next[p][c] == q; p = link[p])next[p][c] = clone;
			link[cur] = link[q] = clone;
		}
	}
	last = cur;
}
char buf[MAXN];
int rank[MAXN], buk[MAXN];
vector<int> G[MAXN];
typedef long long LL;
LL f[MAXN]; //f[s] 状态s以及它的所有祖先匹配的子串的数量。 
void dfs(int u){
	f[u] += 1ll*size[u]*(len[u]-len[link[u]]); 
	for(int i = 0; i < G[u].size(); i++)
		f[G[u][i]] += f[u], dfs(G[u][i]);
}
int main(){
	freopen("find_2016.in", "r", stdin);
	freopen("find_2016.out", "w", stdout);
  scanf("%s", buf);
	for(int i = 0; buf[i]; i++)expand(buf[i]-'a');
	//topo sort
	for(int i = 1; i <= cnt; i++)buk[len[i]]++;
	for(int i = 1; i <= cnt; i++)buk[i] += buk[i-1];
	for(int i = cnt; i; i--)rank[buk[len[i]]--] = i;
	//这里才完成对size的计算 
	for(int i = cnt; i; i--)size[link[rank[i]]] += size[rank[i]];
	for(int i = 1; i <= cnt; i++)
		if(link[i])G[link[i]].push_back(i); //计算f 
	dfs(1);
	scanf("%s", buf);
	LL ans = 0;
	int st = 1, mlen = 0;
	for(int i = 0; buf[i]; i++){
		int c = buf[i]-'a';
    if(next[st][c]){
      mlen++; 
      st = next[st][c];
    }else{
      while(st && !next[st][c])st = link[st];
      if(!st)st = 1, mlen = 0;
      else mlen = len[st]+1, st = next[st][c];
    } //mlen成为第二个串[0,i]与第一个串的最长公共子串的长度
		ans += f[link[st]]; //当前转移到了状态st,状态st的祖先全都可以匹配 
		ans += 1ll*(mlen-len[link[st]])*size[st]; 
			//状态st本身只匹配了(mlen-len[link[st]])*size[st]个。 
	}
	printf("%lld\n", ans);
	return 0;
}