后缀自动机求LCS—

经典题

注意匹配的时候：用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<<][];

    int link[maxn<<];

    int len[maxn<<];

    SAM(){

        cnt=last=;

    }

    void insert(int c){

        int p=last,np=last=++cnt;

        len[np]=len[p]+;

        for(;p&&!nxt[p][c];p=link[p])

            nxt[p][c]=np;

        if(!p){link[np]=;return;}

        int q=nxt[p][c];

        if(len[q]==len[p]+){link[np]=q;return;}

        int clone=++cnt;

        link[clone]=link[q];

        len[clone]=len[p]+;

        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=,Len=strlen(s),cur=,Max=;

        for(int i=;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]+;

                    now=nxt[now][c];

                }

                else {

                    now=;

                    cur=;

                }

            }

            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=;i<len1;i++)

        p.insert(s[i]-'a');

    cout<<p.query(t)<<endl;

}

巴特西

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

最新文章

热门文章