Annihilate(SA)

题目描述

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

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

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

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

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

题解

我是个**，字符集会随着SA往后进行越来越大，数组开小调了俩小时。。

用SAM是板子，但它卡空间，所以把它接起来跑一边SA。

我们按照字典序扫描所有后缀，维护一个数组，表示在当前位置到之前x个串的LCS，每次O(n)更新一遍。

代码

#include<iostream>
#include<cstdio>
#define N 2100002
using namespace std;
char s[N];
int rnk[N],y[N],sa[N],n,x,ji[N],m,tong[N],pre[52],height[N],ans[52][52],tot;
inline void init(int x){
    char c=getchar();
    while(!isalpha(c))c=getchar();
    while(isalpha(c))s[++n]=c,ji[n]=x,c=getchar();
} 
inline void qsort(){
    for(int i=0;i<=m;++i)tong[i]=0;
    for(int i=1;i<=n;++i)tong[rnk[i]]++;
    for(int i=1;i<=m;++i)tong[i]+=tong[i-1];
    for(int i=n;i>=1;--i)sa[tong[rnk[y[i]]]--]=y[i];
}
inline void SA(){
    for(int i=1;i<=n;++i)rnk[i]=s[i],y[i]=i;
    m=200;qsort();
    for(int w=1,p;p<n;m=p,w<<=1){
        p=0;
        for(int i=n-w+1;i<=n;++i)y[++p]=i;
        for(int i=1;i<=n;++i)if(sa[i]>w)y[++p]=sa[i]-w;
        qsort();
        swap(rnk,y);rnk[sa[1]]=p=1;
        for(int i=2;i<=n;++i)rnk[sa[i]]=((y[sa[i-1]]==y[sa[i]])&&(y[sa[i-1]+w]==y[sa[i]+w]))?p:++p;
    }
    for(int i=1;i<=n;++i){
        if(rnk[i]==1)continue;
        int j=max(0,height[rnk[i-1]]-1);
        while(s[i+j]==s[sa[rnk[i]-1]+j])j++;
        height[rnk[i]]=j;
    }
    for(int i=1;i<=n;++i){
       for(int j=1;j<=tot;++j)pre[j]=min(pre[j],height[i]);
       pre[ji[sa[i-1]]]=max(pre[ji[sa[i-1]]],height[i]);
       for(int j=1;j<=tot;++j)ans[ji[sa[i]]][j]=ans[j][ji[sa[i]]]=max(ans[j][ji[sa[i]]],pre[j]);
    }
}
int main(){
    scanf("%d",&tot);
    for(int i=1;i<=tot;++i){init(i);s[++n]=i;}
    SA();
    for(int i=1;i<=tot;++i){
        for(int j=1;j<=tot;++j)if(i!=j)printf("%d ",ans[i][j]);
        puts("");
    }
    return 0;
}