LCS2 – Longest Common Substring II(spoj1812)(sam(后缀自动机)+多串LCS)

A string is finite sequence of characters over a non-empty finite set \(\sum\).

In this problem, \(\sum\) 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:

Notice: new testcases added

题意：

给出多个字符串，求多个串的最长公共子串

题解：

把第一个串建一个后缀自动机，之后把每个串都在上面跑一个\(LCS\)如这个，跑的时候记录每一个点的最大匹配长度。每跑完一个串把当前答案在\(parent\)树上反向拓扑一下，更新每个点在所有答案中的最小答案。最后再取个最大值就行了。

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
char s[N];
int a[N],c[N];
void cmax(int &a,int b){
    a=max(a,b);
}
void cmin(int &a,int b){
    a=min(a,b);
}
struct SAM{
    int last,cnt;
    int size[N],ch[N][26],fa[N<<1],l[N<<1],mx[N<<1],mn[N<<1];
    void ins(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;
            }
        }
        size[np]=1;
    }
    void build(char s[]){
    memset(mn,0x3f,sizeof mn);
        int len=strlen(s+1);
        last=cnt=1;
        for(int i=1;i<=len;++i)ins(s[i]-'a');
    }
    void calc(){
        for(int i=1;i<=cnt;++i)c[l[i]]++;
        for(int i=1;i<=cnt;++i)c[i]+=c[i-1];
        for(int i=1;i<=cnt;++i)a[c[l[i]]--]=i;
    }
    void work(char s[]){
        int len=strlen(s+1);
        int p=1,left=0,as=0;
        while(left<=len){
            left++;
            while(p&&(!ch[p][s[left]-'a']))p=fa[p],as=l[p];
            if(!p)p=1,as=0;
            else{
                as++;
                p=ch[p][s[left]-'a'];
                cmax(mx[p],as);
            }
        }
        for(int i=cnt;i;--i){
            int p=a[i],f=fa[p];
            cmax(mx[f],min(mx[p],l[f]));
            cmin(mn[p],mx[p]);mx[p]=0;
        }
    }
    void tj(){
        int ot=0;
        for(int i=1;i<=cnt;++i)
            cmax(ot,mn[i]);
        cout<<ot<<endl;
    }
}sam;
int main(){
    cin>>s+1;
    sam.build(s);int js=0,ll=strlen(s+1);
    sam.calc();
    while(cin>>s+1)
        sam.work(s);
    sam.tj();
}