CF1043D Mysterious Crime 题解

题意

给定 \(m\) 个 长为 \(n\) 的序列，问它们的公共子串的个数。

\(n\le 10^5,m\le 10\)。

已经死掉的做法

一眼广义后缀自动机。建出后缀自动机，然后在 parent tree 上面跑 dfs。正确性会在下面证明。

但是因为广义 SAM 巨大的常数，蒟蒻的代码跑了 1.5s，卡了两天常数卡不过去/kk

下面是蒟蒻的提交

正解

将广义 SAM 换成 SA。

首先有一个显然的性质：任何子串不会在单个串中出现两次，因为串全都是排列。

于是我们把所有串前后拼接起来，建出 SA，求出 height 数组。

然后我们考虑如何求出答案。

根据定义，一个子串要同时在所有串中出现，才是公共子串。

所以我们用一个长为 \(m\) 窗口在 height 数组上扫，求区间最小值。

现在有两个问题：

1. 不会有一个串在这个窗口中出现了多次，而导致有一个串在窗口没有出现过吗？
   不会。根据上面的性质，如果有一个串的两个后缀同时在这个窗口中出现了，这两个后缀的 LCP 一定为空，对答案没有影响。
2. 会算重吗？
   不会。因为根据上面的性质，任何串都不会出现两次。

于是这道题就做完了。

注意事项

1. 如果 \(m=1\)，要特判，输出 \(\frac{n(n+1)}{2}\)。
2. No long long see your ancestor!!!

代码

#include<bits/stdc++.h>
#define cmp(x,y) (lst[x]==lst[y]&&lst[x+b]==lst[y+b])
using namespace std;
inline int read(){
	int ans=0;bool op=0;char ch=getchar();
	while(ch<'0'||'9'<ch){if(ch=='-')op=1;ch=getchar();}
	while('0'<=ch&&ch<='9'){ans=(ans<<1)+(ans<<3)+(ch^48);ch=getchar();}
	if(op)return -ans;
	return ans;
}
const int maxn=1e6+10;
int n,m;
int len;
int lim,num;
int s[maxn];
int sa[maxn],rk[maxn],ky[maxn],lst[maxn<<1],id[maxn],cnt[maxn];
int hi[maxn];
deque<int>q;
long long ans=0;
signed main(){
	n=read(),m=read();
	if(m==1){
		cout<<((1ll*(n+1)*n)>>1);
		return 0;
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			s[j+(i-1)*n]=read();
		}
	}
	len=n*m,lim=n;
	for(int i=1;i<=len;i++)++cnt[rk[i]=s[i]];
	for(int i=1;i<=lim;i++)cnt[i]+=cnt[i-1];
	for(int i=len;i>=1;i--)sa[cnt[rk[i]]--]=i;
	for(int b=1;b<=len;b<<=1){
		num=0;
		for(int i=len;i>len-b;i--)id[++num]=i;
		for(int i=1;i<=len;i++)if(sa[i]>b)id[++num]=sa[i]-b;
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=len;i++)++cnt[ky[i]=rk[id[i]]];
		for(int i=1;i<=lim;i++)cnt[i]+=cnt[i-1];
		for(int i=len;i>=1;i--)sa[cnt[ky[i]]--]=id[i];
		memcpy(lst+1,rk+1,len*sizeof(int));
		num=0;
		for(int i=1;i<=len;i++)rk[sa[i]]=cmp(sa[i],sa[i-1])?num:++num;
		if(num==len)break;
		lim=num;
	}
	num=0;
	for(int i=1;i<=len;i++){
		if(rk[i]==1)continue;
		if(num)--num;
		while(s[i+num]==s[sa[rk[i]-1]+num])++num;
		hi[rk[i]]=num;
	}
	for(int i=1;i<=len;i++){
		while(!q.empty()&&q.front()<=i-m+1)q.pop_front();
		while(!q.empty()&&hi[q.back()]>=hi[i])q.pop_back();
		q.push_back(i);
		if(i>=m)ans+=hi[q.front()];
	}
	cout<<ans;
	return 0;
}