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

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

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

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 using namespace std; 7 const int mxn=605; 8 int L1[mxn*(1<<12)],L2[mxn*(1<<12)]; 9 queue<int>q1,q2;10 bool vis[mxn][(1<<12)];11 int n;12 int ans[mxn],num=0;13 struct ACa{14     int t[mxn][26];15     int fail[mxn];16     int end[mxn];17     int S,cnt;18     int q[670],hd,tl;19     void init(){S=cnt=1;memset(end,0,sizeof end);return;}20     void insert(char *s,int id){21         int len=strlen(s),now=S;22         for(int i=0;i<len;i++){23             if(!t[now][s[i]-‘A‘])t[now][s[i]-‘A‘]=++cnt;24             now=t[now][s[i]-‘A‘];25         }26         end[now]|=(1<<id);27     }28     void Build(){29         hd=1;tl=0;30         for(int i=0;i<26;i++)31             if(t[S][i]){q[++tl]=t[S][i];fail[t[S][i]]=S;}32             else t[S][i]=S;33         while(hd<=tl){34             int u=q[hd++];35             int v,r;36             for(int i=0;i<26;i++){37                 if(t[u][i]){38                     fail[t[u][i]]=t[fail[u]][i];39                     end[t[u][i]]|=end[t[fail[u]][i]];40                     q[++tl]=t[u][i];41                 }42                 else t[u][i]=t[fail[u]][i];43             }44         }45         return;46     }47     void solve(){48         hd=1;tl=1;int ed=(1<<n)-1;49         q1.push(S),q2.push(0);50         while(hd<=tl){51             int u=q1.front();q1.pop();52             int e=q2.front();q2.pop();53 //            printf("  e:%d\n",e);54             if(e==ed){//结束状态 55                 for(;hd>1;hd=L2[hd]){ans[++num]=L1[hd];}56                 for(int i=num;i;i--)printf("%c",ans[i]+‘A‘);57                 return;58             }59             for(int i=0;i<26;i++){60                 if(!vis[t[u][i]][e|end[t[u][i]]]){61                     L1[++tl]=i;62                     L2[tl]=hd;63                     q1.push(t[u][i]);64                     q2.push(e|end[t[u][i]]);65                     vis[t[u][i]][e|end[t[u][i]]]=1;66                 }67             }68             hd++;69         }70     }71 }ac;72 char s[60];73 int main(){74     int i,j;75     scanf("%d",&n);76     ac.init();77     for(i=0;i<n;i++)scanf("%s",s),ac.insert(s,i);78 //    for(i=1;i<=ac.cnt;i++)if(ac.end[i])printf("%d %d\n",i,ac.end[i]);79     ac.Build();80     ac.solve();81     return 0;82 }