spoj1811 最长公共子串问题 [后缀自动机]

in 题目 with 0 comment

Description

LCS - Longest Common Substring

A string is finite sequence of characters over a non-empty finite set Σ.
In this problem, Σ is the set of lowercase letters.
Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string .Now your task is simple, for two given strings, find the length of the longest common substring of them.
Here common substring means a substring of two or more strings.


Input

The input contains exactly two lines, each line consists of no more than 250000 lowercase letters, representing a string.


Output

The length of the longest common substring. If such string doesn't exist, print "0" instead.


Sample Input

alsdfkjfjkdsal
fdjskalajfkdsla


###Sample Output

3


Solution

后缀自动机模板,对一个串建后缀自动机,另一个串在该自动机上逐位匹配,记录匹配到的最大值


Code

#include<bits/stdc++.h>
#define maxn 500010 
//#define DEBUG
using namespace std;
char a[maxn],b[maxn];

struct SAM
{
    int root,last,tot;
    int fa[maxn],dis[maxn],son[maxn][26];
    SAM()
    {
        root=1,last=1,tot=1;
        memset(fa,0,sizeof(fa));
        memset(dis,0,sizeof(dis));
        memset(son,0,sizeof(son));
    }
    void add(int pos)
    {
        int x=a[pos]-'a',p=last,np = (++tot);
        last=np,dis[np]=pos;
        for( ; p&&!son[p][x] ; p=fa[p] ) son[p][x]=np;
        if(!p) fa[np]=root;
        else
        {
            int q=son[p][x];
            if(dis[q]==dis[p]+1) fa[np]=q;
            else
            {
                int nq= (++tot);
                dis[nq]=dis[p]+1;
                memcpy(son[nq],son[q],sizeof(son[q]));
                fa[nq]=fa[q];
                fa[q]=fa[np]=nq;
                for( ; son[p][x]==q ; p=fa[p] ) son[p][x]=nq;
            }
        }
    }
} S ;

int main()
{
    scanf("%s",a+1);
    scanf("%s",b+1);
    int n=strlen(a+1),m=strlen(b+1);
#ifdef DEBUG
    cerr<<"n="<<n<<" m="<<m<<endl; 
#endif
    for(int i=1;i<=n;++i) S.add(i);
    int len=0,ans=0,p=S.root;
    for(int i=1;i<=m;++i)
    {
        int x=b[i]-'a';
        if(S.son[p][x]) len++,p=S.son[p][x];
        else
        {
            while(p&&!S.son[p][x]) p=S.fa[p];
            if(!p) len=0,p=S.root;
            else len=S.dis[p]+1,p=S.son[p][x];
        }
        ans=max(ans,len);
    }
    printf("%d",ans);
    return 0;
} 

扫描二维码,在手机上阅读!
Responses