欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P5028 Annihilate(SA)

程序员文章站 2022-05-11 23:18:11
...

题目描述

黑暗之主的蜈蚣几乎可以毁灭一切,因此小正方形陷入了苦战……

小正方形现在需要减弱黑暗之主的攻击。

一个黑暗之主的攻击可以用一个仅有小写字母的字符串表示。

现在黑暗之主向小正方形发动了若干攻击,对于两个攻击,小正方形能选出它们最长的公共子串,并把这一段消除。

现在小正方形想要知道,对于任意两个黑暗之主的攻击,它们的最长公共子串长度是多少,你能帮帮它吗?

输入格式

第一行为一个整数 n,表示字符串数目。

接下来 n 行,一行一个字符串,保证所有字符串长度之和 <= 1000000

输出格式

输出共有 n 行,每行 n - 1个正整数

第一行第一个正整数表示第1个串与第2个串的最长公共子串

第二个正整数表示第1个串与第3个串的最长公共子串

……

第二行第一个正整数表示第2个串与第1个串的最长公共子串

以此类推。


题解:
我们把所有串用不同的分隔符连接在一起,用SA得到height数组,用mi[i]表示上一个属于i串的后缀到当前位置的height的最小值,用这个最小值来更新ans[i][j]和ans[j][i],明显是当前的最优解

详解放代码里吧↓


AC代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define LL long long
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
const int MAXN = 1e6+1000;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
int n,la,bel[MAXN]; char s[MAXN],a[MAXN];
struct SA{
    int sa[MAXN],rk[MAXN],y[MAXN],c[MAXN],h[MAXN];
    int ans[55][55],mi[55],vis[55];
    inline void get(int n,int m=150){
        for(int i=0;i<=m;i++) c[i]=0;
        for(int i=1;i<=n;i++) ++c[rk[i]=a[i]];
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--) sa[c[rk[i]]--]=i;
        for(int k=1;k<=n;k<<=1){
            int num=0;
            for(int i=n-k+1;i<=n;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++) c[i]=0;
            for(int i=1;i<=n;i++) ++c[rk[i]];
            for(int i=1;i<=m;i++) c[i]+=c[i-1];
            for(int i=n;i>=1;i--) sa[c[rk[y[i]]]--]=y[i];
            swap(rk,y);
            rk[sa[1]]=num=1;
            for(int i=2;i<=n;i++)
                rk[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k] ? num:++num);
            if(num==n) break;
            m = num;
        }
        for(int i=1,k=0;i<=n;i++){
            if(k) --k; else k=0;
            int j=sa[rk[i]-1];
            while(a[i+k]==a[j+k]) ++k;
            h[rk[i]]=k;
        }
    }
    inline void solve(){
        for(int i=1;i<=la;i++){
            for(int j=1;j<=n;j++){
                mi[j]=min(mi[j],h[i]);//更新每一个lcp最小值
                if(vis[j]) ans[bel[sa[i]]][j]=max(ans[bel[sa[i]]][j],mi[j]);
                //如果这个串之前出现过,那么就可以更新当前位置所对应的串和j串的最长公共子串
            }
            if(bel[sa[i]]) vis[bel[sa[i]]]=true,mi[bel[sa[i]]]=INF;
            //打上标记,表示这个串已经出现过了,顺便重置最小值
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)
                if(i!=j) printf("%d ",max(ans[i][j],ans[j][i]));
            puts("");
        }
    }
}sa;
int main(){
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
#endif // ONLINE_JUDGE
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1); int len=strlen(s+1);
        for(int j=1;j<=len;j++) a[++la]=s[j],bel[la]=i;
        a[++la]='#'+i;
    }
    sa.get(la); sa.solve();
    return 0;
}

相关标签: SA