差异

题目描述

给定一个长度为 $n$ 的字符串 $S$，令 $T_i$ 表示它从第 $i$ 个字符开始的后缀。求

$\displaystyle \sum_{1\leqslant i<j\leqslant n}\text{len}(T_i)+\text{len}(T_j)-2\times\text{lcp}(T_i,T_j)$

其中，$\text{len}(a)$ 表示字符串 $a$ 的长度，$\text{lcp}(a,b)$ 表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。

输入输出格式

输入格式：

一行，一个字符串 $S$。

输出格式：

一行，一个整数，表示所求值。

输入输出样例

输入样例#1：
复制

cacao

输出样例#1：
复制

说明

对于 100% 的数据，保证 $2\leqslant n\leqslant 500000$，且均为小写字母。

分析

参照张天扬《后缀自动及及其应用》。

把串反向，然后求的是前缀串两两的最长公共后缀。定位前缀串在后缀自动机上的位置以后，这个最长公共后缀就是他们在parent树上的lca。

那么简单计数统计即可。时间复杂度$O(n)$

co int N=1e6;

int last=1,tot=1;

int ch[N][26],fa[N],len[N],s[N],w[N];

void extend(int c){

	int p=last,cur=last=++tot;

	len[cur]=len[p]+1,s[cur]=w[cur]=1;

	for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=cur;

	if(!p) fa[cur]=1;

	else{

		int q=ch[p][c];

		if(len[q]==len[p]+1) fa[cur]=q;

		else{

			int clone=++tot;

			memcpy(ch[clone],ch[q],sizeof ch[q]);

			fa[clone]=fa[q],len[clone]=len[p]+1;

			fa[cur]=fa[q]=clone;

			for(;ch[p][c]==q;p=fa[p]) ch[p][c]=clone;

		}

	}

}

char str[N];

int n,cnt[N],id[N];

int main(){

	scanf("%s",str+1),n=strlen(str+1);

	for(int i=n;i>=1;--i) extend(str[i]-'a');

	for(int i=1;i<=tot;++i) ++cnt[len[i]];

	for(int i=1;i<=n;++i) cnt[i]+=cnt[i-1];

	for(int i=1;i<=tot;++i) id[cnt[len[i]]--]=i;

	for(int i=tot;i;--i) s[fa[id[i]]]+=s[id[i]];

	ll ans=0;

	for(int i=1;i<=tot;++i){

		ans+=(ll)w[fa[i]]*s[i]*len[fa[i]];

		w[fa[i]]+=s[i];

	}

	printf("%lld\n",(ll)(n-1)*(n+1)*n/2-2*ans);

	return 0;

}

BZOJ3879 SvT

有一个长度为n的仅包含小写字母的字符串S,下标范围为[1,n].

现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在S中出现的起始位置来表示),求这些后缀两两之间的LCP的长度之和.一对后缀之间的LCP长度仅统计一遍.

对于100%的测试数据,有S<=5*10⁵,且Σt<=3*10⁶.

特别注意:由于另一世界线的某些参数发生了变化,对于一组询问,即使一个后缀出现了多次,也仅算一次.

这题无非是加个虚树而已。

巴特西

AHOI2013 差异和 BZOJ3879 SvT

差异

题目描述

输入输出格式

输入输出样例

说明

分析

BZOJ3879 SvT

最新文章

热门文章

巴特西

AHOI2013 差异 和 BZOJ3879 SvT

差异

题目描述

输入输出格式

输入输出样例

说明

分析

BZOJ3879 SvT

最新文章

热门文章

AHOI2013 差异和 BZOJ3879 SvT