M_sea

SPOJ1811 LCS - Longest Common Substring
SPOJLuogu翻译分析$\mathrm{SAM}$ 。把第一个字符串建成 $\mathrm{SAM}$ ,然后...
扫描右侧二维码阅读全文
26
2019/03

SPOJ1811 LCS - Longest Common Substring

SPOJ

Luogu翻译

分析

$\mathrm{SAM}$ 。

把第一个字符串建成 $\mathrm{SAM}$ ,然后把第二个字符串丢到上面去匹配。

具体的就是:

  • 如果有对应的转移,直接跳。
  • 如果没有对应的转移,在 $\mathrm{parent}$ 树上往上跳,直到这个转移存在。
  • 如果跳到根节点了也不存在该转移,那么从下一位开始重新匹配。

感性理解一下,这样子是最优的

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=250000+10;

char s1[N],s2[N];

//Suffix Automaton
int last,cnt;
int ch[N<<1][26],fa[N<<1],l[N<<1];

inline void extend(int c) {
    int p=last,np=++cnt; last=np,l[np]=l[p]+1;
    for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
    if (!p) fa[np]=1;
    else {
        int q=ch[p][c];
        if(l[p]+1==l[q]) fa[np]=q;
        else {
            int nq=++cnt; l[nq]=l[p]+1;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            fa[nq]=fa[q],fa[q]=fa[np]=nq;
            for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }
    }
}

//main
int main() {
    scanf("%s%s",s1+1,s2+1);
    int l1=strlen(s1+1),l2=strlen(s2+1);
    last=cnt=1;
    for (re int i=1;i<=l1;++i) extend(s1[i]-'a');
    int ans=0;
    for (re int i=1,p=1,now=0;i<=l2;++i) {
        int w=s2[i]-'a';
        while (p&&!ch[p][w]) p=fa[p],now=l[p];
        if (!p) p=1,now=0;
        if (ch[p][w]) p=ch[p][w],++now;
        ans=max(ans,now);
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 24 PM

发表评论