Description
给定n个字符串（S1,S2,?,Sn），要求找到一个最短的字符串T，使得这n个字符串（S1,S2,?,Sn）都是T的子串。
Input
第一行是一个正整数n（n<=12），表示给定的字符串的个数。以下的n行，每行有一个全由大写字母组成的字符串。每个字符串的长度不超过50.
Output
只有一行，为找到的最短的字符串T。在保证最短的前提下，如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。
Sample Input
2
ABCD
BCDABC
ABCD
BCDABC
Sample Output
ABCDABC
HINT
Source
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
状压DP~
因为字符串只有13个，可以使用状压来做。先暴力去掉被包含的字符串，再暴力预处理出每一段接在另一段后面的开始位置，然后状压DP即可~
卡空间，f和s第一维必须输4096,1<<13会被卡T。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;int n,f[4096][13],c[13][13],len[13],cnt,bin[13];
bool b[13];
char a[13][51],s[4096][13][601];bool che(int u,int v,int i)
{for(int j=1;j<=len[v] && i<=len[u];j++,i++)if(a[u][i]!=a[v][j]) return 0;return 1;
}bool in(int u,int v)
{if(len[u]>len[v]) return 0;for(int i=1;i<=len[v]-len[u]+1;i++)if(che(v,u,i)) return 1;return 0;
}int cal(int u,int v)
{for(int i=max(1,len[u]-len[v]+1);i<=len[u];i++)if(che(u,v,i)) return len[v]-len[u]+i-1;return len[v];
}int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%s",a[i]+1),len[i]=strlen(a[i]+1);memset(b,1,sizeof(b));memset(f,0x3f,sizeof(f));for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j && in(i,j)) b[i]=0;for(int i=1;i<=n;i++)if(b[i]) memcpy(a[++cnt],a[i],sizeof(a[i]));n=max(cnt,1);for(int i=1;i<=n;i++) len[i]=strlen(a[i]+1);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) if(i!=j) c[i][j]=cal(i,j);bin[0]=1;for(int i=1;i<=n;i++) bin[i]=bin[i-1]<<1;for(int i=1;i<=n;i++) f[bin[i-1]][i]=len[i],memcpy(s[bin[i-1]][i],a[i],sizeof(a[i]));for(int k=1;k<bin[n];k++)for(int i=1;i<=n;i++)if(k&bin[i-1]){int now=k^bin[i-1];for(int j=1;j<=n;j++)if(j!=i && k&bin[j-1]){if(f[k][i]>f[now][j]+c[j][i]){f[k][i]=f[now][j]+c[j][i];memcpy(s[k][i],s[now][j],sizeof(s[now][j]));int num=strlen(s[now][j]+1);for(int z=len[i]-c[j][i]+1;z<=len[i];z++) s[k][i][++num]=a[i][z];}else if(f[k][i]==f[now][j]+c[j][i]){int num=strlen(s[now][j]+1);bool flag=0;for(int z=1;z<=num;z++)if(s[now][j][z]<s[k][i][z]){flag=1;break;}else if(s[now][j][z]>s[k][i][z]) break;if(flag){memcpy(s[k][i],s[now][j],sizeof(s[now][j]));for(int z=len[i]-c[j][i]+1;z<=len[i];z++) s[k][i][++num]=a[i][z];}}}}int ans=1,x=bin[n]-1;for(int i=2;i<=n;i++)if(f[x][i]<f[x][ans]) ans=i;else if(f[x][i]==f[x][ans]){for(int z=1;z<=f[x][i];z++)if(s[x][i][z]<s[x][ans][z]){ans=i;break;}else if(s[x][i][z]>s[x][ans][z]) break;}int num=strlen(s[x][ans]+1);for(int i=1;i<=num;i++) putchar(s[x][ans][i]);return 0;
}