自动搬运

查看原文

来自洛谷，原作者为

	Tx_Lcy ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็树不要皮，必死无疑；人不要脸，天下无敌

搬运于2025-08-24 22:06:21，当前版本为作者最后更新于2022-12-02 12:35:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

思路

算是一道简单的 $\rm SA$ 题吧，连我这种刚学 $\rm SA$ 一天的菜鸡都会做。

首先，注意到 $n \le 50,\sum |s_i| \le 10^6$，启示我们复杂度可能是 $n \times \sum |s_i|$，不然毒瘤出题人不可能把 $n$ 开的这么小。

根据 $\rm SA$ 题的一贯套路，我们需要把这些串拼起来，然后跑一遍 $\rm SA$ 求出 $\rm height$ 和 $\rm sa$。

注意到如果我们枚举到排名为 $i$ 的后缀，有这么两个数 $j1$ 和 $j2$，钦定 $j1<j2$，那么区间 $j_1,i$ 的最小 $\rm height$ 一定 $\le$ 区间 $j_2,i$ 的最小 $\rm height$，于是，我们只需要对每个 $i\ (1 \le i \le n)$ 维护一个最右指针即可。

如果出题人不卡空间，那么可以直接上 $\rm ST$ 表，不过出题人比较毒瘤，于是我们只能维护一个长度为 $n$ 的数组 $\rm minx_j$ 表示从上一个 $j$ 出现的位置到当前枚举的 $i$ 中 $\rm height$ 的最小值。

最后就是 $\rm SA$ 的实现了，设 $m=\sum |s_i|$。你可以做到 $\mathcal O(m \log m)$，不过我不喜欢动脑子，于是直接 $\mathcal O(m \log^2 m)$，在洛谷评测机状态好的情况下开 $\rm O_2$ 可以过，最慢的点大约 $\rm 1.95 \ s$。

时间复杂度 $\mathcal O(m \log^2 m+nm)$。

代码

#include<bits/stdc++.h>
using namespace std;
int const N=3e6+10;
char k[N];
int rk[N],w,ans[105][105],minx[105],frm[N],sum[N],oldrk[N],sa[N],height[N];
inline bool cmp(int x,int y){return rk[x]==rk[y]?rk[x+w]<rk[y+w]:rk[x]<rk[y];}
inline void SA(string s){
	int n=s.length();s=" "+s;
	for (int i=1;i<=n;++i) k[i]=s[i];
	sort(k+1,k+n+1);
	for (int i=1;i<=n;++i) rk[i]=lower_bound(k+1,k+n+1,s[i])-k,sa[i]=i;
	for (w=1;w<n;w<<=1){
		sort(sa+1,sa+n+1,cmp);
		for (int i=1;i<=n;++i) oldrk[i]=rk[i];
		for (int p=0,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;
	}
	for (int i=1;i<=n;++i) rk[sa[i]]=i;
	int k=0;
	for (int i=1;i<=n;++i){
		if (k) --k;int j=sa[rk[i]-1];
		while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;
		height[rk[i]]=k;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n;cin>>n;string ss="";
	for (int i=1;i<=n;++i){
		string s;cin>>s;
		int len=s.length();
		s=" "+s;for (int j=1;j<=len;++j)
			ss+=s[j],frm[ss.length()]=i;
		ss+=char(i+26);
	}
	SA(ss);int m=ss.length();
	for (int i=2;i<=m;++i){
		for (int j=1;j<=n;++j) minx[j]=min(minx[j],height[i]);
		minx[frm[sa[i-1]]]=height[i];
		int now=frm[sa[i]];
		for (int j=1;j<=n;++j) ans[now][j]=ans[j][now]=max(ans[now][j],minx[j]);
	}
	for (int i=1;i<=n;++i,cout<<'\n')
		for (int j=1;j<=n;++j)
			if (i^j) cout<<ans[i][j]<<' ';
	return 0;
}

$\rm upd$：有一个 $\rm s$ 写成 $\rm ms$ 了，希望管理能重新审核一下。