最长公共子串(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; }

 

上一篇:算法导论 — 2.3 设计算法


下一篇:Luogu2251 质量检测 (ST表)