题目概述

HDU2328

解题报告

首先将所有串中间隔开接起来（注意中间隔开的字符不能相同）。

二分枚举答案 $len$ ，然后根据 $Height$ 数组分块，每个块中检查是否 $n$ 个字符串都出现了。

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=804000,maxm=4000;

int m,n,pos,s[maxn+5],ID[maxn+5];char str[maxn+5];
int SA[maxn+5],rk[maxn+5],t[(maxn<<1)+5],ha[maxn+5],H[maxn+5];
int ti,vis[maxm+5];

void Sort(int n,int m){
    for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++;
    for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[t[i]]]--]=t[i];
}
void Make(int n,int m=255){
    for (int i=1;i<=n;i++) rk[i]=s[i],t[i]=i,t[i+n]=0;Sort(n,m);
    for (int k=1,p=0;p<n;k<<=1,m=p){
        p=0;for (int i=n-k+1;i<=n;i++) t[++p]=i;
        for (int i=1;i<=n;i++) if (SA[i]>k) t[++p]=SA[i]-k;
        Sort(n,m);for (int i=1;i<=n;i++) t[i]=rk[i];rk[SA[1]]=p=1;
        for (int i=2;i<=n;i++) rk[SA[i]]=(p+=t[SA[i]]!=t[SA[i-1]] || t[SA[i]+k]!=t[SA[i-1]+k]);
    }
    for (int i=1,k=0;i<=n;i++) {if (k) k--;while (s[i+k]==s[SA[rk[i]-1]+k]) k++;H[rk[i]]=k;}
}
bool check(int len){
    for (int i=1,j;i<=n;i=j){
        int now=1;vis[ID[SA[i]]]=++ti;
        for (j=i+1;j<=n && H[j]>=len;j++) if (vis[ID[SA[j]]]<ti) now++,vis[ID[SA[j]]]=ti;
        if (now==m) {pos=SA[i];return true;}
    }
    return false;
}
int main(){
    freopen("2328.in","r",stdin);freopen("2328.out","w",stdout);
    for (scanf("%d",&m),n=0;m;scanf("%d",&m),n=0){
        for (int i=1,ch=27;i<=m;i++){
            scanf("%s",str+1);
            for (int j=1;str[j];j++) s[++n]=str[j]-'a'+1,ID[n]=i;
            s[++n]=++ch;
        }
        s[n]=0;Make(n,m+26);int L=1,R=200;
        for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
            check(mid)?L=mid+1:R=mid-1;
        if (!R) puts("IDENTITY LOST");
        else {for (int i=pos;i<pos+R;i++) putchar(s[i]+'a'-1);puts("");}
    }
    return 0;
}