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();

}

秒客网