后缀自动机求LCS——spoj-LCS

落日映苍穹つ 2023-10-11 09:14 30阅读 0赞

经典题

注意匹配的时候：用t串去s串的SAM里进行匹配，和字典树一样遍历t中字符，用cur记录当前已经匹配的长度，如果能当前字符能匹配则cur++(这里不能直接用cur=len\[now\]),反之用link指针进行失配，直到完成匹配后cur=len\[now\]

**为什么匹配成功时不能直接cur=len\[now\]?因为自动机上的转移是在后面加一个字符，但是不保证前面不加字符，因为每个结点的len是该节点代表的maxlen**

**但是失配后再转移成功则可以用cur=len\[now\],因为失配结点代表的最短串长度都有len\[now\]+1，即到了这个状态，那么t串一定有minlen\[now\]的长度,所以其link指向的状态的maxlen\[now\]=minlen\[now-1\]一定是满足条件的！**

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 250005
    struct SAM{
        int cnt,last;
        int nxt[maxn<<1][26];
        int link[maxn<<1];
        int len[maxn<<1];
        SAM(){
            cnt=last=1;
        }
        void insert(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 query(char *s){
            int now=1,Len=strlen(s),cur=0,Max=0;
            for(int i=0;i<Len;i++){
                int c=s[i]-'a';
                if(nxt[now][c]){
                    now=nxt[now][c];
                    cur++;
                }
                else {
                    while(now && !nxt[now][c])now=link[now];
                    if(now){
                        cur=len[now]+1;
                        now=nxt[now][c];
                    }
                    else {
                        now=1;
                        cur=0;
                    }
                }
                Max=max(Max,cur); 
            }
            return Max;
        }
    }p;
    char s[maxn],t[maxn];
    
    int main(){
        scanf("%s%s",s,t);
        int len1=strlen(s);
        int len2=strlen(t);
        for(int i=0;i<len1;i++)
            p.insert(s[i]-'a');
        cout<<p.query(t)<<endl;
    }

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