Corporate Identity
题意：
求n个字符串的最长公共子串。
分析：
考虑最简单的情况，求两个字符串的最长公共子串。同理，我们这里也对字符串进行拼接，求出height数组，然后对height数组进行遍历，找到一段区间的所有数都大于等于len且区间内包括来自n个字符串的后缀，len所能达到的最大值即是这个最长公共子串的长度。现在我们想想为什么这么做是对的？首先明确一点，height数组是排名相邻的后缀的最长公共前缀的长度。考虑到如果a与b的最长公共前缀的长度为len1，b与c的最长公共前缀为len2，那么a与b的前len1个字符是相同的，b与c的前len2个字符是相同的，a与c的前min（len1，len2）个字符是相同的。那么对于一段连续的区间，它的最小height值即是这段区间内对应的所有后缀的最长公共前缀的长度，如果这些后缀包含了来自n个字符串的后缀，那么我们可以说它是n个字符串一个公共子串的长度。所以我们只需要找出所有这样的区间，取其中的最大值即可。
开始时我们是根据最长公共子串的长度len来找到一段最大连续区间（区间内包括来自n个字符串的后缀，且所有数大于等于len），因为现在我们不知道这个len，所以我们就二分枚举这个len，判断当前len下是否能找到满足上述要求的区间，求出最大的len值，输出对应区间的任意一个后缀的前len个字符就好了。
代码：
#include <map> #include <queue> #include <math.h> #include <string> #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define ull unsigned long long #define cls(x) memset(x,0,sizeof(x)) #define clslow(x) memset(x,-1,sizeof(x)) const int maxm=210; const int maxn=4000*maxm; int n,cnt; char s[maxm]; bool vis[maxn]; //block[i]:表示以第i个字符开始的后缀属于第几个字符串 int r[maxn],block[maxn]; int sa[maxn],Rank[maxn],height[maxn]; namespace Suffix { int wa[maxn],wb[maxn],wv[maxn],wt[maxn]; int cmp(int *r,int a,int b,int k) { return r[a]==r[b]&&r[a+k]==r[b+k]; } void da(int *r,int *sa,int n,int m) { int i,j,p,*x=wa,*y=wb,*t; for(i=0; i<m; i++) wt[i]=0; for(i=0; i<=n; i++) wt[x[i]=r[i]]++; for(i=1; i<m; i++) wt[i]+=wt[i-1]; for(i=n; i>=0; i--) sa[--wt[x[i]]]=i; p=1; j=1; for(; p<=n; j*=2,m=p) { for(p=0,i=n+1-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<=n; i++) wv[i]=x[y[i]]; for(i=0; i<m; i++) wt[i]=0; for(i=0; i<=n; i++) wt[wv[i]]++; for(i=1; i<m; i++) wt[i]+=wt[i-1]; for(i=n; i>=0; i--) sa[--wt[wv[i]]]=y[i]; t=x; x=y; y=t; x[sa[0]]=0; for(p=1,i=1; i<=n; i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)? p-1:p++; } } void getheight(int *r,int* sa,int n) { int i,j,k=0; for(i=1; i<=n; i++) Rank[sa[i]]=i; for(i=0; i<n; i++) { if(k) k--; else k=0; j=sa[Rank[i]-1]; while(r[i+k]==r[j+k]) k++; height[Rank[i]-1]=k; } } }; //判断是否存在这样一个区间的所有值大于等于len，且包含 //了来自n个字符串的后缀 bool judge(int len,int& pos) { int tot=0; for(int j=0;j<=n;j++) vis[j]=false; for(int i=1;i<cnt;i++){ if(i<cnt-1&&height[i]>=len){ int b1=block[sa[i]],b2=block[sa[i+1]]; if(!vis[b1]) tot++; vis[b1]=true; if(!vis[b2]) tot++; vis[b2]=true; } else{ if(tot>=n){ pos=sa[i-1]; return true; } tot=0; for(int j=0;j<=n;j++) vis[j]=false; } } return false; } //二分找出最长公共字串的长度 int binary_Search(int& pos) { int ans=-1; int l=1,r=maxm; while(l<=r) { int mid=(l+r)>>1; if(judge(mid,pos)){ l=mid+1; ans=mid; } else r=mid-1; } return ans; } int main() { // freopen("in.txt","r",stdin); while(scanf("%d",&n)!=EOF&&n) { cnt=0; //字符串拼接 for(int i=1;i<=n;i++){ scanf("%s",s); int slen=strlen(s); for(int j=0;j<slen;j++){ block[cnt]=i; r[cnt++]=s[j]-'a'; } r[cnt++]=29+i; } //求得height数组 r[cnt]=0; Suffix::da(r,sa,cnt,30+n); Suffix::getheight(r,sa,cnt); int pos=-1; int reval=binary_Search(pos); if(reval==-1) printf("IDENTITY LOST "); else{ for(int i=pos;i<pos+reval;i++){ printf("%c",r[i]+'a'); } printf(" "); } } return 0; }