给定n个字符串（S1,S2,„,Sn），要求找到一个最短的字符串T，使得这n个字符串（S1,S2,„,Sn）都是T的子串。

第一行是一个正整数n（n<=12），表示给定的字符串的个数。以下的n行，每行有一个全由大写字母组成的字符串。每个字符串的长度不超过50.

只有一行，为找到的最短的字符串T。在保证最短的前提下，如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。

 1 #include<cstdio> 2 #define N 605 3 #define M (1<<12) 4 #define chr char 5 #define sht short 6 chr s[55]; 7 int n,tt=1; 8 sht fl[N]; 9 int ed[N];10 sht ch[N][26];11 int q[N*M],l,r;12 sht f[N][M];13 int p[N][M];14 sht c[N][M];15 sht stk[N],tp;16 main(){17     scanf("%d",&n);18     for(int i=0;i<n;++i){19         scanf("%s",s); int t=1;20         for (char *c=s;*c;++c){21             if(!ch[t][*c-‘A‘])22                 ch[t][*c-‘A‘]=++tt;23             t=ch[t][*c-‘A‘];24         }25         ed[t]|=1<<i;26     }27     fl[1]=1;28     for(int i=0;i<26;++i)29         if(ch[1][i])30             fl[q[r++]=ch[1][i]]=1;31         else32             ch[1][i]=1;33     while(l!=r){34         int t=q[l++];35         for(int i=0;i<26;++i)36             if(ch[t][i])37                 fl[q[r++]=ch[t][i]]=ch[fl[t]][i],38                 ed[ch[t][i]]|=ed[ch[fl[t]][i]];39             else40                 ch[t][i]=ch[fl[t]][i];41     }42     l=r=0;q[r++]=1<<n;f[1][0]=1;43     while(l!=r){44         int id=q[l]>>n,bt=q[l]&((1<<n)-1);++l;45         for(int i=0;i<26;++i){46             int v=ch[id][i],b=bt|ed[v];47             if(f[v][b])continue;48             f[v][b]=1;q[r++]=v<<n|b; 49             p[v][b]=id<<n|bt;50             c[v][b]=i;51             if(b==(1<<n)-1)goto out;52         }53     }54 out:int id=q[r-1]>>n,bt=(1<<n)-1;55     while(id!=1){56         stk[++tp]=c[id][bt];57         int pp=p[id][bt];58         id=pp>>n;59         bt=pp&((1<<n)-1);60     }61     while(tp)putchar(‘A‘+stk[tp--]);puts("");62 }