SPOJ1811 [字尾自動機]

題目

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.

輸入

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

輸出

The length of the longest common substring. If such string doesn’t exist, print “0” instead.

樣例輸入

alsdfkjfjkdsal

fdjskalajfkdsla

樣例輸出

3

分析

字尾自動機模闆,對一個串建字尾自動機,另一個串在該自動機上逐位比對,記錄比對到的最大值

代碼

#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][];
    SAM()
    {
        root=,last=,tot=;
        memset(fa,,sizeof(fa));
        memset(dis,,sizeof(dis));
        memset(son,,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]+) fa[np]=q;
            else
            {
                int nq= (++tot);
                dis[nq]=dis[p]+;
                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+);
    scanf("%s",b+);
    int n=strlen(a+),m=strlen(b+);
#ifdef DEBUG
    cerr<<"n="<<n<<" m="<<m<<endl; 
#endif
    for(int i=;i<=n;++i) S.add(i);
    int len=,ans=,p=S.root;
    for(int i=;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=,p=S.root;
            else len=S.dis[p]+,p=S.son[p][x];
        }
        ans=max(ans,len);
    }
    printf("%d",ans);
    return ;
}