spoj1812 Longest Common Substring II（LCS2），后缀自动机

1811LCS的升级版。

求十个串的最长连续公共子串。

第一个串建立自动机。

用其它每个串在自动机上跑一遍，记录每个状态上能匹配的最长长度。

然后求每个状态匹配长度的最小值。

注意每个状态能匹配的，每个状态的父节点也能匹配。

利用拓扑排序（按照len），从深到浅依次更新父亲的匹配长度。

由于spoj实在是太搓，这一步要用基数排序，或者是O（n）的拓扑排序来实现。

很坑的是各种数组记得开成两倍长。后缀自动机总节点数最多是长度两倍。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define Maxn 110000

int root,last;//sam
int tots;

struct sam_node{
    int fa,son[26];
    int len;
    void init(int _len){len=_len;fa=-1;memset(son,-1,sizeof(son));}
}t[Maxn*2];//length*2

void sam_init(){
    tots=0;
    root=last=0;
    t[tots].init(0);
}

void extend(char ch){
    int w=ch-'a';
    int p=last;
    int np=++tots;t[tots].init(t[p].len+1);
    int q,nq;

    while(p!=-1&&t[p].son[w]==-1){t[p].son[w]=np;p=t[p].fa;}
    if (p==-1) t[np].fa=root;
    else{
        q=t[p].son[w];
        if (t[p].len+1==t[q].len){t[np].fa=q;}
        else{
            nq=++tots;t[nq].init(0);
            t[nq]=t[q];
            t[nq].len=t[p].len+1;
            t[q].fa=nq;t[np].fa=nq;
            while(p!=-1&&t[p].son[w]==q){t[p].son[w]=nq;p=t[p].fa;}
        }
    }
    last=np;
}

const int inf=1010000000;
char s[Maxn];
char f[11][Maxn];
int ma[11][Maxn*2];

void work(int num){
    int l=strlen(f[num]);
    int i,w;
    int tl=0,tt=0,p=root;

    for(i=0;i<l;++i){
        w=f[num][i]-'a';
        while(t[p].fa!=-1&&t[p].son[w]==-1){p=t[p].fa;tt=t[p].len;}
        if (t[p].son[w]!=-1) {
            tt++;
            p=t[p].son[w];
            ma[num][p]=ma[num][p]<tt?tt:ma[num][p];
        }
        else {p=root;tt=0;}

    }
}

int w[Maxn*2],st[Maxn*2];

int main(){
    int l,n,i,j,ans,tma,u;
    scanf("%s",s);
    n=0;
    while(scanf("%s",f[n+1])!=EOF){n++;}

    sam_init();
    l=strlen(s);
    for(i=0;i<l;++i) extend(s[i]);
    memset(ma,0,sizeof(ma));
    for(i=1;i<=n;++i) work(i);
    //printf("tots=%d\n",tots);

    for(i=0;i<=l;++i)   w[i]=0;
    for(i=1;i<=tots;++i)w[t[i].len]++;
    for(i=1;i<=l;++i)   w[i]+=w[i-1];
    for(i=tots;i>=1;--i)st[w[t[i].len]--]=i;

    for(i=tots;i>=1;--i){
        u=st[i];
        //printf(" %d\n",u);
        if (t[u].fa!=-1)
        for(j=1;j<=n;++j){
            ma[j][t[u].fa]=min(t[t[u].fa].len,max(ma[j][t[u].fa],ma[j][u]));
        }
    }

    ans=0;
    for(i=1;i<=tots;++i){
        tma=t[i].len;
        for(j=1;j<=n;++j){
            if (ma[j][i]<tma) tma=ma[j][i];
        }
        if (tma>ans) ans=tma;
    }
    printf("%d\n",ans);
    return 0;
}