最长公共子串(LCS) lg SP1811

后缀自动机的一大用处就是求最长公共子串了

这道题的话题意就是给你两个字符串，求最长公共子串

做法的话是先使用一个字符串建立SAM，然后让另一个串在上面进行匹配

匹配的策略是优先匹配当前节点的下一个字符，如果没有可以匹配的，就沿着parent树向上跳，如果到根了，就重新初始化重新开始搜，如果不是根就往下跳，把len更新为node[p].len+1（这个是因为我只是比p节点的串长1，而不是完全匹配选一个节点的最长长度）

具体的解释放在代码中吧

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<3)+(w<<1)+ch-48;
        ch=getchar();
    }
    return w*f;
}
int n,m,lst=1,tot=1;
int l1,l2;
long long size[2000010];
struct Node{
    int len,fa;
　　 map<int,int> ch;//因为有的题字符集可能比较大，开个map其实还是比较舒服的
}node[2000010];
inline void extend(int now){//这个建SAM的过程是常规操作
    int p=lst;tot++;lst=tot;int np=tot;
    node[np].len=node[p].len+1;
    while(p&&!node[p].ch[now]){
        node[p].ch[now] = np;
        p = node[p].fa;
    }
    if(!p) node[np].fa = 1;
    else{
        int q = node[p].ch[now];
        if(node[q].len == node[p].len + 1){
            node[np].fa=q;
        }
        else{
            int nq=++tot;
            node[nq]=node[q];
            node[nq].len=node[p].len+1;
            node[np].fa = node[q].fa = nq;
            while(p && node[p].ch[now] == q){
                node[p].ch[now] = nq;
                p = node[p].fa;
            }
        }
    }
}
char s[2000010],t[2000010];int ans=0;
int main(){
    scanf("%s%s",s+1,t+1);int i,j,k;
    l1=strlen(s+1),l2=strlen(t+1);
    for(i=1;i<=l1;i++){
        extend(s[i]-'a'+1);
    }//建出第一个串的SAM
    int p=1;int len=0;//初始化，让当前指针到根，长度设为0
    for(i=1;i<=l2;i++){
        int now=t[i]-'a'+1;
        if(node[p].ch[now]){//匹配策略见我上面的注释
            p=node[p].ch[now];len++;
        }
        else{
            while(p&&!node[p].ch[now]){
                p=node[p].fa;
            }
            if(!p){
                p=1;len=0;
            }
            else{
                len=node[p].len+1;p=node[p].ch[now];
            }
        }
        ans=max(ans,len);
    }
    cout<<ans<<endl;
    return 0;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：最长公共子串(LCS) lg SP1811，转载请注明来源！

赞 0

　分享到：