给定n个字符串（S1,S2,„,Sn），要求找到一个最短的字符串T，使得这n个字符串（S1,S2,„,Sn）都是T的子串。
给定n个字符串（S1,S2,„,Sn），要求找到一个最短的字符串T，使得这n个字符串（S1,S2,„,Sn）都是T的子串。
第一行是一个正整数n（n<=12），表示给定的字符串的个数。以下的n行，每行有一个全由大写字母组成的字符串。每个字符串的长度不超过50.
只有一行，为找到的最短的字符串T。在保证最短的前提下，如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。
不明白网上为啥题解都写的那么复杂，还说可以hack别人，好怕怕哦……
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 else 32 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 else 40 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 }
@Author: YouSiki
原文：http://www.cnblogs.com/yousiki/p/6498304.html