spoj lcs2.cpp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 500050
using namespace std;
struct node{
    node*go[26],*fa;
    int l,num,lcs,nlcs;
}sam[N],*root=sam,*last=sam;
int cur;
void expand(int x)
{
    cur++;node*p=&sam[cur],*tp=last;p->num=cur;
    p->lcs=p->l=tp->l+1;last=p;
    for(;tp&&!tp->go[x];tp=tp->fa)tp->go[x]=p;
    if(!tp){
        p->fa=root;
    }else{
        if(tp->go[x]->l==tp->l+1)p->fa=tp->go[x];
        else{
            cur++;node*r=&sam[cur],*q=tp->go[x];
            *r=*q;r->num=cur;r->l=r->lcs=tp->l+1;
            r->fa=q->fa;q->fa=p->fa=r;
            for(;tp&&tp->go[x]==q;tp=tp->fa)tp->go[x]=r;
        }
    }
}
char st[N];
int d[N];
node* b[N];
int main()
{
    root=last=&sam[cur=0];
    scanf("%s",st);int ans=strlen(st);
    for(int i=0;i<ans;i++)expand(st[i]-'a');
    int len=ans;
    for(int i=0;i<=cur;i++) d[sam[i].l]++;
    for(int i=1;i<=len;i++) d[i]+=d[i-1];
    for(int i=0;i<=cur;i++) b[--d[sam[i].l]]=&sam[i];
    while(scanf("%s",st)!=EOF)
    {
        len=strlen(st);
        last=root;int l=0;
        for(int i=0;i<len;i++)
        {
            if(last->go[st[i]-'a'])l++,last=last->go[st[i]-'a'];
            else {
                while(last&&!last->go[st[i]-'a'])last=last->fa;
                if(!last)last=root,l=0;
                else{
                    l=last->l+1;
                    last=last->go[st[i]-'a'];
                    
                }
            }last->nlcs=max(last->nlcs,l);
        }
        for(int i=cur;i;i--)b[i]->lcs=min(b[i]->lcs,b[i]->nlcs),b[i]->fa->nlcs=max(b[i]->fa->nlcs,b[i]->nlcs),b[i]->nlcs=0;
     }
     ans=0;
     for(int i=0;i<=cur;i++)ans=max(ans,sam[i].lcs);
     printf("%d\n",ans);
     return 0;
}