[文章目录]
Description
给定n个字符串（S1,S2,„,Sn），要求找到一个最短的字符串T，使得这n个字符串（S1,S2,„,Sn）都是T的子串。n<=12 len<=50
KMP。
KMP将n个字符串中作为别的字符串的子串的剔除。那么发现答案只能是原n个串的一个全排列，将其顺次首尾相接去掉公共前缀后缀所构成的串。
KMP预处理任意两个串的最长公共前后缀的长度然后状压DP即可。
对于第二关键字最小字典序，记录DP路径path，在长度相同时比较即可。
复杂度O(2^n*n^2*len)
好像AC自动机也能做且更好。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,mp[15][15],z1[15],z2[15],dp[1<<13][13],path[1<<13][13];
bool vis[15];
char s[15][60],st1[700],st2[700];
inline int getlen(char *x,char *y)
{
static int nxt[60];
int i=0,k=-1,len=strlen(x); nxt[0]=-1;
while(i<len)
{
if(k==-1||x[i]==x[k]) nxt[++i]=++k;
else k=nxt[k];
}
i=k=0; int lim=strlen(y);
while(i<len&&k<lim)
{
if(i==-1||x[i]==y[k]) i++,k++;
else i=nxt[i];
if(i==len) return len;
}
return i;
}
inline bool cmp(char *x,char *y)
{
int len=min(strlen(x),strlen(y));
for(int i=0;i<len;++i)
if(x[i]!=y[i]) return x[i]<y[i];
return strlen(x)<strlen(y);
}
inline void output(int z[],int tail,char *st)
{
int Len=0; z[tail+1]=0;
for(int i=tail;i>0;--i)
{
for(int j=mp[z[i]][z[i+1]];j<(int)strlen(s[z[i]]);++j)
st[Len++]=s[z[i]][j];
}
st[Len++]='\0';
}
inline bool find(int S,int x,int y)
{
int t1=0,t2=0,tmp=S;
while(x!=-1)
{
z1[++t1]=x+1;
tmp-=(1<<x);
x=path[tmp+(1<<x)][x];
}
tmp=S;
while(y!=-1)
{
z2[++t2]=y+1;
tmp-=(1<<y);
y=path[tmp+(1<<y)][y];
}
output(z1,t1,st1); output(z2,t2,st2);
return cmp(st1,st2);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%s",s[i]);
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
{
if(strlen(s[i])<strlen(s[j])&&getlen(s[i],s[j])==(int)strlen(s[i])) vis[i]=1;
else if(getlen(s[j],s[i])==(int)strlen(s[j])) vis[j]=1;
}
int m=0; for(int i=1;i<=n;++i) if(!vis[i]) memcpy(s[++m],s[i],sizeof(s[i]));
n=m;
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) mp[i][j]=getlen(s[i],s[j]);
static int a[15],b[15],len[15];
for(int i=1;i<=n;++i) len[i]=strlen(s[i]);
memset(dp,0x3f,sizeof dp);
for(int i=1;i<=n;++i) dp[1<<(i-1)][i-1]=len[i],path[1<<(i-1)][i-1]=-1;
int s1,s2;
for(int S=1;S<(1<<n);++S)
{
a[0]=b[0]=0;
for(int i=0;i<n;++i)
{
if((S>>i)&1) a[++a[0]]=i;
else b[++b[0]]=i;
}
for(int i=1;i<=a[0];++i)
for(int j=1;j<=b[0];++j)
{
s1=a[i]; s2=b[j];
m=dp[S][s1]+len[s2+1]-mp[s2+1][s1+1];
if( m < dp[S|(1<<s2)][s2]
|| (m==dp[S|(1<<s2)][s2] && find(S,s1,path[S|(1<<s2)][s2]) ) )
dp[S|(1<<s2)][s2]=m,path[S|(1<<s2)][s2]=s1;
}
}
m=(1<<n)-1; int ans1=inf,ans=0;
for(int i=0;i<n;++i)
if(dp[m][i]<ans1||(dp[m][i]==ans1&&find(m,i,ans)))
ans1=dp[m][i],ans=i;
a[0]=0;
while(ans!=-1)
{
a[++a[0]]=ans+1;
ans1=ans;
ans=path[m][ans];
m-=(1<<ans1);
}
output(a,a[0],st1); printf("%s",st1);
return 0;
}