题解

思路分析

这是一道 后缀数组 + ST表 + 容斥原理 的字符串问题。

问题建模

• $N$ 头牛，每头牛有一个名字（字符串）
• 对于每头牛，计算其独有的子串数量（其他牛的名字都不包含该子串）

核心思路

1. 总子串数

对于长度为 $L$ 的字符串，子串总数为 $\frac{L(L+1)}{2}$。

2. 后缀数组统计重复

将所有字符串拼接（用不同的分隔符），构建后缀数组。

对于每个位置 $i$：

• 它能贡献 $n - sa[i] + 1$ 个子串
• 但其中 $he[i]$ 个与前一个后缀重复

关键：统计每个子串被多少个不同的牛包含。

3. 容斥计算独有子串

对于牛 $i$ 的每个后缀：

• 总子串数 = $n - sa[j] + 1$（$sa[j]$ 属于牛 $i$）
• 减去与相邻后缀的 LCP（避免重复计数）
• 减去被其他牛也包含的子串

4. ST表优化查询

使用 ST 表（Sparse Table）快速查询区间最小 LCP。

算法步骤

1. 拼接字符串：

   • 将所有牛的名字用不同分隔符拼接
   • 记录每个位置属于哪头牛

2. 后缀数组 + height：

   • 构建后缀数组
   • 计算 height 数组

3. ST表预处理：

   • 对 height 数组建 ST 表
   • 支持 $O(1)$ 查询区间最小值

4. 统计独有子串：

   • 对于每头牛，遍历其所有后缀
   • 使用 ST 表计算与其他牛后缀的最大 LCP
   • 容斥计算独有子串数

5. 输出答案

复杂度分析

• 后缀数组：$O(L \log L)$，$L$ 为总长度
• ST 表：$O(L \log L)$
• 统计：$O(L)$
• 总时间复杂度：$O(L \log L)$
• 空间复杂度：$O(L \log L)$

#include <bits/stdc++.h>
#define N 500001
using namespace std;
int n;
int a[N];long long ans[N];
int sa[N],rk[N],oldrk[N],he[N];
int cnt[N],id[N],st[N][30];
int pos[N];
char tmp[N];
int s[N];
void getsa(){
	int m=400000;
	for (int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;
	for (int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for (int i=n;i;i--)sa[cnt[rk[i]]--]=i;
	for (int w=1,p=0;;w<<=1,m=p,p=0){
		for (int i=n-w+1;i<=n;i++)id[++p]=i;
		for (int i=1;i<=n;i++)if (sa[i]>w)id[++p]=sa[i]-w;
		memset(cnt,0,sizeof cnt);
		for (int i=1;i<=n;i++)cnt[rk[i]]++;
		for (int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for (int i=n;i;i--)sa[cnt[rk[id[i]]]--]=id[i];
		p=0;
		memcpy(oldrk,rk,sizeof rk);
		for (int i=1;i<=n;i++){
			if (oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w]){
				rk[sa[i]]=p;
			}else{
				rk[sa[i]]=++p;
			}
		}
		if (p==n)break;
	}
}
void gethe(){
	for (int i=1,k=0;i<=n;i++){
		if (!rk[i])continue;
		if (k)k--;
		while (s[i+k]==s[sa[rk[i]-1]+k])++k;
		he[rk[i]]=k;
	}
}
int query(int l,int r){
	l++;
	int k=log2(r-l+1);
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
signed main(){
	cin>>n;
	int tmpn=0;
	for (int i=1;i<=n;i++){
		scanf("%s",tmp+1);
		int len=1;
		for (;tmp[len];len++){
			s[++tmpn]=tmp[len];
			pos[tmpn]=i;
		}
		len--;
		s[++tmpn]='z'+i;
		ans[i]=1ll*len*(len+1)/2;
	}
	s[tmpn--]=0;
	swap(n,tmpn);
	getsa();
	gethe();
	for (int i=1;i<=n;i++)st[i][0]=he[i];
	for (int j=1;(1<<j)<=n;j++){
		for (int i=1;i+(1<<j)-1<=n;i++){
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
	int lst=0,last=0;
	for (int i=n;i;i--){
		if (pos[sa[i]]!=pos[sa[last]]){
			lst=last;
		}
		last=i;
		a[i]=(lst<=i?0:query(i,lst));
	}
	for (int i=1;i<=n;i++){
		ans[pos[sa[i]]]-=max(a[i],he[i]);
	}
	for (int i=1;i<=tmpn;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

题解

把所有字符串用不同的分隔符拼接成一个大串，并记录每个后缀属于哪头牛。所有分隔符都大于 'z'，因此不会与原串的字符混淆。对大串建立后缀数组及 height（LCP） 数组，再用 ST 表维护区间 LCP 的最小值，便可以在 O(1) 时间求出任意两个后缀的最长公共前缀长度。

单独来看某头牛的名字，若长度为 len，它一共有 len(len+1)/2 个子串。为了得到“不同因子”，只需扣掉那些与其他字符串有公共前缀的子串长度。设 sa[i] 的后缀属于字符串 id，我们找到与它相邻且属于不同字符串的后缀，取两者的 LCP 作为这条后缀被别人“覆盖”的最大长度。更精确地，为了找出真正的最大 LCP，我们需要定位到左边最近、右边最近属于其它字符串的后缀，通过 RMQ 求得与它们的 LCP，再取最大值。该长度即为从当前后缀延伸出的、不能算作“独有”的子串数量。

把每个后缀贡献的长度按所属字符串累加，就可以得到每头牛需要扣掉的数量，差值便是答案。由于后缀数组与 RMQ 的构建都是线性的，整个算法的时间复杂度为 O(|S| log |S|)，其中 |S| 是所有字符串长度之和。

#include <bits/stdc++.h>
#define N 500001
using namespace std;
int n;
int a[N];long long ans[N];
int sa[N],rk[N],oldrk[N],he[N];
int cnt[N],id[N],st[N][30];
int pos[N];
char tmp[N];
int s[N];
void getsa(){
	int m=400000;
	for (int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;
	for (int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for (int i=n;i;i--)sa[cnt[rk[i]]--]=i;
	for (int w=1,p=0;;w<<=1,m=p,p=0){
		for (int i=n-w+1;i<=n;i++)id[++p]=i;
		for (int i=1;i<=n;i++)if (sa[i]>w)id[++p]=sa[i]-w;
		memset(cnt,0,sizeof cnt);
		for (int i=1;i<=n;i++)cnt[rk[i]]++;
		for (int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for (int i=n;i;i--)sa[cnt[rk[id[i]]]--]=id[i];
		p=0;
		memcpy(oldrk,rk,sizeof rk);
		for (int i=1;i<=n;i++){
			if (oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w]){
				rk[sa[i]]=p;
			}else{
				rk[sa[i]]=++p;
			}
		}
		if (p==n)break;
	}
}
void gethe(){
	for (int i=1,k=0;i<=n;i++){
		if (!rk[i])continue;
		if (k)k--;
		while (s[i+k]==s[sa[rk[i]-1]+k])++k;
		he[rk[i]]=k;
	}
}
int query(int l,int r){
	l++;
	int k=log2(r-l+1);
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
signed main(){
	cin>>n;
	int tmpn=0;
	for (int i=1;i<=n;i++){
		scanf("%s",tmp+1);
		int len=1;
		for (;tmp[len];len++){
			s[++tmpn]=tmp[len];
			pos[tmpn]=i;
		}
		len--;
		s[++tmpn]='z'+i;
		ans[i]=1ll*len*(len+1)/2;
	}
	s[tmpn--]=0;
	swap(n,tmpn);
	getsa();
	gethe();
	for (int i=1;i<=n;i++)st[i][0]=he[i];
	for (int j=1;(1<<j)<=n;j++){
		for (int i=1;i+(1<<j)-1<=n;i++){
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
	int lst=0,last=0;
	for (int i=n;i;i--){
		if (pos[sa[i]]!=pos[sa[last]]){
			lst=last;
		}
		last=i;
		a[i]=(lst<=i?0:query(i,lst));
	}
	for (int i=1;i<=n;i++){
		ans[pos[sa[i]]]-=max(a[i],he[i]);
	}
	for (int i=1;i<=tmpn;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}