【SPOJ1812】LCS2 – 徐亦轲的博客

多串的最长公共子串

我们仍然对其中一个建后缀自动机，再拿另外的串分别在后缀自动机上面跑。因为每个串包含的子串是不同的，所以我们要把信息记录在后缀自动机上。对于每一个在后缀自动机上跑过的串，记录它在每个点时的最大匹配长度。那么我们就可以知道每个点表示的串中哪些出现了。同时我们沿\(fail\)链将最大匹配长度上传（如果非\(0\)），因为\(fail\)链上的父亲一定是其后缀，一定也都出现了，所以父亲的最大匹配长度直接等于其\(len\)值即可。

// <1811.cpp> - 01/16/17 11:14:36
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=200010;
const int INF=1e9;
const int K=26;
char ch[MAXN];
int tot,np;
int f[MAXN],s[MAXN][K];
int len[MAXN];
void insert(int x){
    int p=np;len[np=++tot]=len[p]+1;
    for(;!s[p][x];p=f[p])s[p][x]=np;
    int q=s[p][x];
    if(len[q]==len[p]+1)f[np]=q;
    else{
        int nq=++tot;
        memcpy(s[nq],s[q],sizeof(s[q]));
        f[nq]=f[q];len[nq]=len[p]+1;
        f[q]=f[np]=nq;
        for(;s[p][x]==q;p=f[p])s[p][x]=nq;
    }
}
int id[MAXN],sum[MAXN];
int tmp[MAXN],ans[MAXN];
int main(){
    scanf("%s",ch+1);
    int n=strlen(ch+1);
    tot=np=1;
    for(int i=0;i<K;i++)s[0][i]=1;len[0]=-1;
    for(int i=1;i<=n;i++)insert(ch[i]-'a');
    for(int i=1;i<=tot;i++)ans[i]=INF;
    for(int i=1;i<=tot;i++)sum[len[i]]++;
    for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
    for(int i=1;i<=tot;i++)id[sum[len[i]]--]=i;
    while(~scanf("%s",ch+1)){
        n=strlen(ch+1);
        int p=1,now=0;
        for(int i=1;i<=n;i++){
            int x=ch[i]-'a';
            for(;!s[p][x];p=f[p])now=len[f[p]];
            p=s[p][x];
            tmp[p]=max(tmp[p],++now);
        }
        for(int i=tot;i;i--){
            int x=id[i];
            ans[x]=min(ans[x],tmp[x]);
            if(tmp[x])tmp[f[x]]=len[f[x]];
            tmp[x]=0;
        }
        for(int i=1;i<=tot;i++)tmp[i]=0;
    }
    int ANS=0;
    for(int i=1;i<=tot;i++)ANS=max(ANS,ans[i]);
    printf("%d",ANS);
    return 0;
}

// <1811.cpp> - 01/16/17 11:14:36

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=200010;

const int INF=1e9;

const int K=26;

char ch[MAXN];

int tot,np;

int f[MAXN],s[MAXN][K];

int len[MAXN];

void insert(int x){

int p=np;len[np=++tot]=len[p]+1;

for(;!s[p][x];p=f[p])s[p][x]=np;

int q=s[p][x];

if(len[q]==len[p]+1)f[np]=q;

else{

int nq=++tot;

memcpy(s[nq],s[q],sizeof(s[q]));

f[nq]=f[q];len[nq]=len[p]+1;

f[q]=f[np]=nq;

for(;s[p][x]==q;p=f[p])s[p][x]=nq;

}

int id[MAXN],sum[MAXN];

int tmp[MAXN],ans[MAXN];

int main(){

scanf("%s",ch+1);

int n=strlen(ch+1);

tot=np=1;

for(int i=0;i<K;i++)s[0][i]=1;len[0]=-1;

for(int i=1;i<=n;i++)insert(ch[i]-'a');

for(int i=1;i<=tot;i++)ans[i]=INF;

for(int i=1;i<=tot;i++)sum[len[i]]++;

for(int i=1;i<=n;i++)sum[i]+=sum[i-1];

for(int i=1;i<=tot;i++)id[sum[len[i]]--]=i;

while(~scanf("%s",ch+1)){

n=strlen(ch+1);

int p=1,now=0;

for(int i=1;i<=n;i++){

int x=ch[i]-'a';

for(;!s[p][x];p=f[p])now=len[f[p]];

p=s[p][x];

tmp[p]=max(tmp[p],++now);

}

for(int i=tot;i;i--){

int x=id[i];

ans[x]=min(ans[x],tmp[x]);

if(tmp[x])tmp[f[x]]=len[f[x]];

tmp[x]=0;

}

for(int i=1;i<=tot;i++)tmp[i]=0;

}

int ANS=0;

for(int i=1;i<=tot;i++)ANS=max(ANS,ans[i]);

printf("%d",ANS);

return 0;

}