[bzoj1195][DP]最短母串

本文主要是介绍[bzoj1195][DP]最短母串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

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

Input

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

Output

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

Sample Input

2

ABCD

BCDABC

Sample Output

ABCDABC

题解

先把包含的情况去掉
状压 $f [i] [j]$ 表示状态为 $i$ ，最后一个串是 $j$ 的时候的最小长度
大力转移…
比较恶心的就是字典序
每次dp的时候你就返回去把串给搞出来
暴力判
带了个500的常数…不会很大的

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#define LL long long
#define mp(x,y) make_pair(x,y)
using namespace std;
inline int read()
{int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
inline void write(int x)
{if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');
}
inline void print(int x){write(x);printf(" ");}
int n,f[(1<<12)+5][13],bin[25],len[25];
int pre[(1<<12)+5][13];
char ch[13][55],fac[13][55];
int sum[13][13];
char c1[5500],c2[5500];
int sta[5500],ttp;
bool check(int u1,int p1,int u2,int p2)
{sta[ttp=1]=p1;while(u1)sta[++ttp]=pre[u1][p1],u1=u1^bin[p1],p1=sta[ttp];int l1=0,pa;while(ttp){if(!l1)pa=1;else pa=sum[sta[ttp+1]][sta[ttp]]+1;while(pa<=len[sta[ttp]])c1[++l1]=fac[sta[ttp]][pa++];ttp--;}c1[l1+1]='\0';sta[ttp=1]=p2;while(u2)sta[++ttp]=pre[u2][p2],u2=u2^bin[p2],p2=sta[ttp];l1=0,pa;while(ttp){if(!l1)pa=1;else pa=sum[sta[ttp+1]][sta[ttp]]+1;while(pa<=len[sta[ttp]])c2[++l1]=fac[sta[ttp]][pa++];ttp--;}c2[l1+1]='\0';if(strcmp(c1+1,c2+1)>0)return false;return true;
}
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);bin[1]=1;for(int i=2;i<=20;i++)bin[i]=bin[i-1]<<1;n=read();for(int i=1;i<=n;i++)scanf("%s",ch[i]+1);int tp=0;for(int i=1;i<=n;i++){bool bk=false;for(int j=1;j<=tp;j++)if(strstr(fac[j]+1,ch[i]+1)){bk=true;break;}for(int j=i+1;j<=n;j++)if(strstr(ch[j]+1,ch[i]+1)){bk=true;break;}if(!bk){tp++;for(int j=1;j<=strlen(ch[i]+1);j++)fac[tp][j]=ch[i][j];}}n=tp;for(int i=1;i<=tp;i++)len[i]=strlen(fac[i]+1);for(int i=1;i<=tp;i++)for(int j=1;j<=tp;j++)if(i!=j){int l1=strlen(fac[i]+1),l2=strlen(fac[j]+1);for(int k=1;k<=l1;k++)if(fac[i][k]==fac[j][1]){bool tf=false;for(int l=1;k+l-1<=l1;l++)if(fac[i][k+l-1]!=fac[j][l]){tf=true;break;}if(!tf){sum[i][j]=l1-k+1;break;}}}memset(f,63,sizeof(f));f[0][0]=0;for(int i=1;i<=tp;i++)f[bin[i]][i]=len[i];for(int i=1;i<bin[tp+1];i++)for(int j=1;j<=tp;j++)if(i&bin[j])for(int k=1;k<=tp;k++)if((i&bin[k])&&k!=j){if(f[i^bin[j]][k]+len[j]-sum[k][j]<f[i][j])f[i][j]=f[i^bin[j]][k]+len[j]-sum[k][j],pre[i][j]=k;else if(f[i^bin[j]][k]+len[j]-sum[k][j]==f[i][j]&&f[i][j]<1e9){if(check(i^bin[j],k,i,j))f[i][j]=f[i^bin[j]][k]+len[j]-sum[k][j],pre[i][j]=k;}}int ans=999999999,h1;for(int i=1;i<=tp;i++){if(ans>f[bin[tp+1]-1][i])ans=f[bin[tp+1]-1][i],h1=i;else if(ans==f[bin[tp+1]-1][i])if(check(bin[tp+1]-1,i,bin[tp+1]-1,h1))h1=i;}int p1=h1,u1=bin[tp+1]-1;sta[ttp=1]=p1;while(u1)sta[++ttp]=pre[u1][p1],u1=u1^bin[p1],p1=sta[ttp];int l1=0,pa;while(ttp){if(!l1)pa=1;else pa=sum[sta[ttp+1]][sta[ttp]]+1;while(pa<=len[sta[ttp]])c1[++l1]=fac[sta[ttp]][pa++];ttp--;}for(int i=1;i<l1;i++)printf("%c",c1[i]);printf("%c\n",c1[l1]);
//	printf("%d\n",ans);return 0;
}