SP10570 LONGCS - Longest Common Substring
提供一个后缀数组解法。
多字符串，中间加分隔符然后后缀排序求出 $sa$ 和 $height$。把每个字符串对应的位置染上颜色，问题变为寻找 $i,j$ 使得区间 $[i,j]$ 包含 $n$ 种颜色并且 $\min_{k=i+1}^{j}height_k$ 最大。可以从后向前扫一遍，枚举左端点，寻找合法的最靠左的右端点，颜色数可以开桶维护。对于区间 $\min$，由于左右端点单调不增，所以可以单调队列。复杂度 $\mathcal O(len\log len+len)$，瓶颈在于后缀排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int T,n,m,len,le,maxn,col[500020],height[500020],sa[500020],rk[500020],x[500020],xx[500020],y[500020],t[500020];
char s[500020];
deque<int> q;
inline void mian()
{
read(T);
while(T--)
{
read(n),m=128,memset(col,0,sizeof(col)),len=maxn=0,memset(t,0,sizeof(t));
for(int i=1;i<=n;++i)
{
scanf("%s",s+1),le=strlen(s+1);
for(int j=1;j<=le;++j)++t[x[++len]=s[j]],col[len]=i;
if(i!=n)++t[x[++len]=++m];
}
if(n==1){write(le,'\n');continue;}
memcpy(xx,x,sizeof(x)),swap(n,len);
for(int i=2;i<=m;++i)t[i]+=t[i-1];
for(int i=1;i<=n;++i)sa[t[x[i]]--]=i;
for(int k=1,num=0;k<=n;k<<=1,num=0)
{
for(int i=n;i>n-k;--i)y[++num]=i;
for(int i=1;i<=n;++i)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=1;i<=m;++i)t[i]=0;
for(int i=1;i<=n;++i)++t[x[i]];
for(int i=1;i<=m;++i)t[i]+=t[i-1];
for(int i=n;i>=1;--i)sa[t[x[y[i]]]--]=y[i];
swap(x,y),x[sa[1]]=1;
for(int i=2;i<=n;++i)
{
if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=x[sa[i-1]];
else x[sa[i]]=x[sa[i-1]]+1;
}
if((m=x[sa[n]])==n)break;
}
for(int i=1;i<=n;++i)rk[sa[i]]=i;
for(int i=1,k=0;i<=n;k?--k:0,++i)
{
while(xx[i+k]==xx[sa[rk[i]-1]+k])++k;
height[rk[i]]=k;
}
memset(t,0,sizeof(t));
while(!q.empty())q.pop_back();
for(int i=n-len+1,sum=0,r=n-len+1;i>=1;--i)
{
if(col[sa[i]]&&!t[col[sa[i]]]++)++sum;
while(r>=i&&sum==len&&t[col[sa[r]]]!=1)--t[col[sa[r--]]];
while(!q.empty()&&q.front()>r)
q.pop_front();
if(sum==len)maxn=max(maxn,height[q.front()]);
while(!q.empty()&&height[q.back()]>height[i])q.pop_back();
q.eb(i);
}
write(maxn,'\n');
}
}