后缀自动机求多串LCS——spojlcs2

深藏阁楼爱情的钟 2023-10-11 09:13 23阅读 0赞

/*
    每个状态存最长匹配长度，然后多个串匹配过程中取最小的最长匹配长度
    和LCS1不同的地方：LCS只要维护住当前匹配长度和最长匹配长度即可，但是多串匹配需要维护的是每个状态结点(即后缀树上)的信息 
    所以对每个状态存下两个值Max，Min，分别表示该状态对于该串的最长匹配长度，以及所有已经匹配过的串在该状态下的最小的最长匹配长度 
    在对一个串进行匹配后，在后缀树上自底向上回溯一次，更新Max值
    更新完Max后再更新Min 
    */
    #include<bits/stdc++.h>
    using namespace std;
    #define maxn 400005
    struct SAM{
        int last,cnt;
        int nxt[maxn][26],len[maxn],link[maxn];
        SAM(){last=cnt=1;}
        void add(int c){
            int p=last,np=last=++cnt;
            len[np]=len[p]+1;
    
            for(;p&&!nxt[p][c];p=link[p])
                nxt[p][c]=np;
            if(!p){link[np]=1;return;}
            
            int q=nxt[p][c];
            if(len[q]==len[p]+1){link[np]=q;return;}
            
            int clone=++cnt;
            link[clone]=link[q];
            len[clone]=len[p]+1;
            memcpy(nxt[clone],nxt[q],sizeof nxt[q]);
            link[q]=link[np]=clone;
            for(;p&&nxt[p][c]==q;p=link[p])
                nxt[p][c]=clone;
        }
        int Min[maxn],Max[maxn],t[maxn],id[maxn];
        void sort(){
            for(int i=1;i<=cnt;i++)t[len[i]]++;
            for(int i=1;i<=cnt;i++)t[i]+=t[i-1];
            for(int i=1;i<=cnt;i++)id[t[len[i]]--]=i;
            for(int i=1;i<=cnt;i++)Min[i]=len[i];
        }
        void update(char *s){
            memset(Max,0,sizeof Max);
            int now=1,cur=0,Len=strlen(s);
            for(int i=0;i<Len;i++){
                int p=s[i]-'a';
                if(nxt[now][p]){
                    cur++;
                    now=nxt[now][p];
                }else {
                    while(now && !nxt[now][p])
                        now=link[now];
                    if(now){
                        cur=len[now]+1;
                        now=nxt[now][p];
                    }else {
                        cur=0;now=1;
                    }
                }
                Max[now]=max(Max[now],cur);
            }
            for(int i=cnt;i>=1;i--){
                int tmp=id[i];
                Max[link[tmp]]=max(Max[link[tmp]],Max[tmp]);
            }
            for(int i=cnt;i>=1;i--)
                Min[i]=min(Min[i],Max[i]);
        }
        int calc(){
            int res=0;
            for(int i=1;i<=cnt;i++)res=max(res,Min[i]);
            return res;
        }
    }p;
    char s[maxn];
    int main(){
        cin>>s;
        int len=strlen(s);
        for(int i=0;i<len;i++)p.add(s[i]-'a');
        p.sort();
        while(scanf("%s",s)!=EOF)
            p.update(s);
        cout<<p.calc()<<endl;
    }

转载于:https://www.cnblogs.com/zsben991126/p/11318745.html