題意:給你最多100個字符串,求最長的且是一半以上的字符串的公共子串,如果有多個,按字典序輸出。
思路:先把各個串拼起來,中間加上一個之前未出現過的字符,然後求後綴。然後根據h數組和sa數組,求出最長的公共串。
#include<stdio.h> #include<string.h> #include<algorithm> using std::sort; #define V 220000 int r[V],sa[V],h[V],a[V],b[V],X[V],Y[V]; int acl[120],len[110],tot,mark[V],mark_len,be[V],m[110],max_len; char s[V],out1[V],out2[V]; void calh(int n) { int i,j,k=0; for(i=1; i<=n; i++)r[sa[i]]=i; for(i=0; i<n; h[r[i++]]=k) for(k? k-- :0,j=sa[r[i]-1];a[i+k]==a[j+k];k++); } bool cmp(int *r,int a,int b,int le) { return (r[a]==r[b]&&r[a+le]==r[b+le]); } void suffix(int n,int m=128) { int i,j,*x=X,*y=Y,*t,p; for(i=0;i<m;i++)b[i]=0; for(i=0;i<n;i++)b[x[i]=a[i]]++; for(i=1;i<m;i++)b[i]+=b[i-1]; for(i=n-1;i>=0;i--)sa[--b[x[i]]]=i; for(j=1,p=1;p<n;m=p,j<<=1) { 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++)b[i]=0; for(i=0; i<n;i++)b[x[y[i]]]++; for(i=1; i<m;i++)b[i]+=b[i-1]; for(i=n-1;i>=0;i--)sa[--b[x[y[i]]]]=y[i]; for(t=x,x=y,y=t,x[sa[0]]=0,i=1,p=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; } calh(n-1); } void judge(int n)//先預處理每個sa屬於哪個串 { int i,j,k; for(i=1;i<=n;i++) { for(j=1;j<=tot;j++) { if(sa[i]==len[j]){ be[i]=0; break; } if(sa[i]<len[j]){ be[i]=j; break; } } } } int mm[110]; int getmin(int s)//排序得到當前最長的公共串長度 { for(int i=1;i<=tot;i++)mm[i]=m[i]; sort(mm+1,mm+1+tot); return mm[tot+1-s]; } void solve(int n) { int cou=tot/2+1,cur=0,cur_len=0,i,j;//cou表示至少需要的串的數量,cur表示目前的子串所在的串的數量,cur_len表示目前子串的長度 judge(n); memset(m,0,sizeof(m));//m表示各個串包含的子串的長度 for(i=1;i<=n;i++) { for(j=1;j<=tot;j++)if(m[j]>h[i])//更新mi m[j]=h[i]; if(h[i]<max_len){ cur=0;continue; } if(h[i]>m[be[i]]){ if(m[be[i]]==0||m[be[i]]<max_len)cur++; m[be[i]]=h[i]; } if(h[i]>m[be[i-1]]){ if(m[be[i-1]]==0||m[be[i-1]]<max_len)cur++; m[be[i-1]]=h[i]; } if(cur>=cou){ cur_len=getmin(cou); if(cur_len>max_len) { mark_len=1; mark[0]=sa[i]; max_len=cur_len; } else if(cur_len==max_len) mark[mark_len++]=sa[i]; } } } int main() { int i,j,k,t,n; for(i=1;i<=96;i++)acl[i]=i; for(i=97;i<=110;i++)acl[i]=i+26; while(scanf("%d",&t)!=-1&&t) { len[0]=-1; for(i=1;i<=t;i++) { scanf("%s",s+len[i-1]+1); len[i]=strlen(s); s[len[i]]=acl[i]; } s[len[t]]=0; n=strlen(s); for(i=0;i<n;i++)a[i]=s[i]; a[n]=0; suffix(n+1); mark_len=0;max_len=0;tot=t; solve(n); if(max_len==0) printf("?\n\n"); else{ strcpy(out1,s+mark[0]); out1[max_len]=0; puts(out1); for(i=1;i<mark_len;i++){ strcpy(out2,s+mark[i]); out2[max_len]=0; if(strcmp(out1,out2)==0)continue; strcpy(out1,out2); puts(out1); } puts(""); } } return 0; }