后缀自动机求多个串的最长公共子串+拓补排序讲解+LCS2 - Longest Common Substring II

「爱情、让人受尽委屈。」 2023-06-05 15:53 6阅读 0赞

网上所有关于后缀自动机拓补排序的文章，都默认读者会拓补排序，简直了。

后缀自动机的拓补排序，就是按照长度进行排序，在进行特定操作的时候，通过较长的后缀来更新较短的后缀。那么也就是通过拓补排序中排名靠后的（排名靠后，那么长度一定比较长，），更新排名靠前的（更新他们的父亲）。

AC 代码：

//1:建立后缀自动机
    //2:拓补排序
    //3:将其他串在后缀自动机上跑
    //4:然后对于后缀自动机的每个节点，如果父亲被匹配到孩子被匹配的次数，是父亲的次数和自己的最大值
    //5:遍历数组，取出最大值
    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int M=2e5+5;
    struct Node{int ch[26],fa,len;}sam[M];
    int n,las=1,cnt=1,res[M],t[M],rk[M],sum[M];
    char s[M];
    
    inline void add(int c){
        int p = las; int np = las = ++cnt;
        sam[np].len = sam[p].len + 1;
        for(; p && !sam[p].ch[c]; p = sam[p].fa) sam[p].ch[c] = np;
        if(!p) sam[np].fa = 1;
        else{
            int q = sam[p].ch[c];
            if(sam[q].len == sam[p].len + 1) sam[np].fa = q;
            else{
                int nq = ++cnt; sam[nq] = sam[q];
                sam[nq].len = sam[p].len + 1;
                sam[q].fa = sam[np].fa = nq;
                for(; p && sam[p].ch[c] == q; p = sam[p].fa) sam[p].ch[c] = nq;
            }
        }
    }
    int main(){
        scanf("%s",s+1);
        n=strlen(s+1);
        for(int i=1;i<=n;i++)add(s[i]-'a');
        for(int i=1;i<=cnt;i++) t[sam[i].len]++;
        for(int i=1;i<=cnt;i++) t[i]+=t[i-1];
        for(int i=1;i<=cnt;i++) rk[t[sam[i].len]--]=i;
        for(int i=1;i<=cnt;i++) res[i]=sam[i].len;
    
        while(scanf("%s",s+1)!=EOF){
            n=strlen(s+1);
            for(int i=0;i<=cnt;i++)sum[i]=0;
            for(int p=1,len=0,i=1;i<=n;i++){
                if(sam[p].ch[s[i]-'a'])++len,p=sam[p].ch[s[i]-'a'];
                else {
                    while(p&&!sam[p].ch[s[i]-'a'])p=sam[p].fa;
                    if(!p)p=1,len=0;
                    else len=sam[p].len+1,p=sam[p].ch[s[i]-'a'];
                }
                sum[p]=max(sum[p],len);
            }
            for(int i=cnt;i;i--)sum[sam[rk[i]].fa]=max(sum[sam[rk[i]].fa],sum[rk[i]]);//在自动机上的节点，选择最大值
            for(int i=1;i<=cnt;i++)res[i]=min(sum[i],res[i]);
        }
        res[0]=0;
        for(int i=1;i<=cnt;i++)res[0]=max(res[0],res[i]);
        printf("%d",res[0]);
        return 0;
    }