P5028 Annihilate

· · 题解

题目传送门

思路

算是一道简单的 \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;
}