hdu 2328 Corporate Identity

題目大意：求多串的最長公共子串，並輸出字典序最小。

題目思路：後綴數組，二分答案。

[cpp]
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<string> 
#include<queue> 
#include<algorithm> 
#include<vector> 
#include<stack> 
#include<list> 
#include<iostream> 
#include<map> 
using namespace std; 
#define inf 0x3f3f3f3f 
#define M 810000 
int max(int a,int b) 
{ 
    return a>b?a:b; 
} 
int min(int a,int b) 
{ 
    return a<b?a:b; 
} 
int height[M],rank[M],r[M],sa[M]; 
int ts[M],ta[M],tb[M],tv[M],pos[M],st,ed; 
int rec[10000],flag[10000]; 
bool cmp(int *y,int a,int b,int l) 
{ 
    return y[a]==y[b]&&y[a+l]==y[b+l]; 
} 
void da(int n,int m) 
{ 
    int i,j,*x=ta,*y=tb,p; 
    for(i=0;i<m;i++) ts[i]=0; 
    for(i=0;i<n;i++) ts[x[i]=r[i]]++; 
    for(i=1;i<m;i++) ts[i]+=ts[i-1]; 
    for(i=n-1;i>=0;i--) sa[--ts[x[i]]]=i; 
    for(j=1,p=1;p<n;j*=2,m=p) 
    { 
        p=0; 
        for(i=n-j;i<n;i++) y[p++]=i; 
        for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j; 
        for(i=0;i<m;i++) ts[i]=0; 
        for(i=0;i<n;i++) tv[i]=x[y[i]]; 
        for(i=0;i<n;i++) ts[tv[i]]++; 
        for(i=1;i<m;i++) ts[i]+=ts[i-1]; 
        for(i=n-1;i>=0;i--) sa[--ts[tv[i]]]=y[i]; 
        swap(x,y); 
        x[sa[0]]=0; 
        p=1; 
        for(i=1;i<n;i++) 
        { 
            if(cmp(y,sa[i-1],sa[i],j)) x[sa[i]]=p-1; 
            else x[sa[i]]=p++; 
        } 
    } 
} 
void calh(int n) 
{ 
    int i,k,tmp; 
    for(i=1;i<=n;i++) rank[sa[i]]=i; 
    k=0; 
    for(i=0;i<n;i++) 
    { 
        tmp=sa[rank[i]-1]; 
        for(;r[i+k]==r[tmp+k];k++) 
        ; 
        height[rank[i]]=k; 
        k?--k:0; 
    } 
} 
int check(int n,int len,int tnum) 
{ 
    int i,j,cnt=0,tmp; 
    for(i=0;i<tnum;i++) flag[i]=0; 
    tmp=pos[sa[1]]; 
    flag[tmp]=1;rec[cnt++]=tmp; 
    for(i=2;i<=n;i++) 
    { 
        tmp=pos[sa[i]]; 
        if(height[i]<len) 
        { 
            for(j=0;j<cnt;j++) 
                flag[rec[j]]=0; 
            cnt=0; 
            rec[cnt++]=tmp; 
            flag[tmp]=1; 
        } 
        else 
        { 
            if(!flag[tmp]) 
            { 
                rec[cnt++]=tmp; 
                flag[tmp]=1; 
            } 
            if(cnt==tnum) 
            { 
                st=sa[i]; 
                ed=sa[i]+len; 
                return true; 
            } 
        } 
    } 
    return false; 
} 
char s[M]; 
char str[220]; 
int main() 
{ 
    int i,j,n,tlen,len; 
    while(scanf("%d",&n),n) 
    { 
        tlen=0; 
        for(i=0;i<n;i++) 
        { 
            scanf("%s",str); 
            len=strlen(str); 
            for(j=0;j<len;j++) 
            { 
                r[tlen+j]=str[j]-'a'+4100; 
                pos[tlen+j]=i; 
            } 
            if(i<n-1) 
            r[tlen+len]=i+1; 
            else r[tlen+len]=0; 
            pos[tlen+len]=i; 
            tlen+=len+1; 
        } 
        for(i=0;i<n;i++) flag[i]=0; 
        da(tlen,4500); 
        calh(tlen-1); 
        int le,ri,mid; 
        le=1;ri=len; 
        while(le<=ri) 
        { 
            mid=(le+ri)>>1; 
            if(check(tlen-1,mid,n)) le=mid+1; 
            else ri=mid-1; 
        } 
        if(ri==0) 
            puts("IDENTITY LOST"); 
        else 
        { 
            for(i=st;i<ed;i++) 
            printf("%c",r[i]-4100+'a'); 
            puts(""); 
        } 
    } 
}