题目大意：求多串的最长公共子串，并输出字典序最小。
题目思路：后缀数组，二分答案。
[cpp] #include #include #include #include #include #include #include #include #include #include #include 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 } 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 for(i=0;i for(i=1;i for(i=n-1;i>=0;i--) sa[--ts[x[i]]]=i; for(j=1,p=1;p { p=0; for(i=n-j;i for(i=0;i=j) y[p++]=sa[i]-j; for(i=0;i for(i=0;i for(i=0;i for(i=1;i 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 { 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 { 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 tmp=pos[sa[1]]; flag[tmp]=1;rec[cnt++]=tmp; for(i=2;i<=n;i++) { tmp=pos[sa[i]]; if(height[i] { for(j=0;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 { scanf("%s",str); len=strlen(str); for(j=0;j { r[tlen+j]=str[j]-'a'+4100; pos[tlen+j]=i; } if(i r[tlen+len]=i+1; else r[tlen+len]=0; pos[tlen+len]=i; tlen+=len+1; } for(i=0;i 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 printf("%c",r[i]-4100+'a'); puts(""); } } }