spoj1812-Longest Common Substring II(后缀自动机)

Description

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 a bit harder, for some 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 at most 10 lines, each line consists of no more than 100000 lowercase letters, representing a string.

Output

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

Example

Input:
alsdfkjfjkdsal
fdjskalajfkdsla
aaaajfaaaa

Output:
2

题意：给若干个字符串，长度不超过100000，求最长公共连续字串
解析：后缀自动机，对输入的第一个字符串建一个后缀自动机，在
sam中添加两个量Max[i](查询时以第i个节点为最后一个字符的后缀的最大长度)
，Min[i](所有查询Max[i]中的最小值)。

代码

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int maxn=200005;
struct SAM
{
    int ch[maxn][26];
    int pre[maxn],step[maxn];
    int last,id;
    int Min[maxn],Max[maxn];
    void init() //初始化
    {
        last=id=0;
        memset(ch[0],-1,sizeof(ch[0]));
        pre[0]=-1; step[0]=0;
        Min[0]=Max[0]=0;
    }
    void Insert(int c) //模板,自己百度
    {
        int p=last,np=++id;
        step[np]=step[p]+1;
        memset(ch[np],-1,sizeof(ch[np]));
        Min[np]=Max[np]=step[np];
        while(p!=-1&&ch[p][c]==-1)  ch[p][c]=np,p=pre[p];
        if(p==-1) pre[np]=0;
        else
        {
            int q=ch[p][c];
            if(step[q]!=step[p]+1)
            {
                int nq=++id;
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                step[nq]=step[p]+1;
                Min[nq]=Max[nq]=step[nq];
                pre[nq]=pre[q];
                pre[np]=pre[q]=nq;
                while(p!=-1&&ch[p][c]==q) ch[p][c]=nq,p=pre[p];
            }
            else pre[np]=q;
        }
        last=np;
    }
    void Find(char *S)
    {
        int len=strlen(S);
        int u=0,d=0;
        for(int i=0;i<=id;i++) Max[i]=0;
        for(int i=0;i<len;i++)
        {
            int c=S[i]-'a';
            if(ch[u][c]!=-1) d++,u=ch[u][c];
            else
            {
                while(u!=-1&&ch[u][c]==-1) u=pre[u];
                if(u!=-1) d=step[u]+1,u=ch[u][c];
                else u=0,d=0;
            }
            Max[u]=max(Max[u],d);//更新
        }
        for(int i=id;i>=1;i--) Max[pre[i]]=max(Max[pre[i]],Max[i]);
        for(int i=0;i<=id;i++) Min[i]=min(Min[i],Max[i]);
    }
    int GetAns()
    {
        int ret=0;
        for(int i=0;i<=id;i++) ret=max(ret,Min[i]);
        return ret;
    }
}sam;
char S[maxn];
int main()
{
    scanf("%s",S);
    int len=strlen(S);
    sam.init();
    for(int i=0;i<len;i++) sam.Insert(S[i]-'a');
    while(scanf("%s",S)!=EOF) sam.Find(S);
    printf("%d
",sam.GetAns());
    return 0;
}