给定$n$个01串，求最短的字符串包含这$n$个01串，同时，字符串中不可以出现指定串。
$n \leq 10$ all sting’s length $\leq 6e4$
终于不是裸题了
这题怎么感觉要两个自动机。。
瞎比搞到一个自动机上去
dp[i][j][k]:第$i$个点，已经得到了01串的状态为$j$，在自动机上第$k$个点
然而滚出状态时，$i$最大为$6e4$,自动机上也至多有那么多节点，TLE是板子眼上的东西。
来瞎比优化一下。
那个$i$的维度可以直接存到dp数组里
但是照原来那么高你只能每次添加1步
所以先把从这个串到那个串需要最少添加的字符预处理出来(bfs)
然后瞎比状压就莫名AC啦。。
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define bug(x) cout<<#x<<"="<<x<<" "
#define debug(x) cout<<#x<<"="<<x<<endl
#define downline cout<<"_____________________"<<endl
#define upline cout<<"~~~~~~~~~~~~~~~~~~~~~"<<endl
struct node{
int to[2],g,fr,fv;
}tr[(int)6e4+5];
int n,m,allc,cnt;
char str[(int)5e4+5];
inline void Min(int &a,int b){
if(a==-1||a>b)a=b;
}
int que[(int)6e4+5],dp[1<<11][11],pos[11];
inline void Insert(int id){
int len=strlen(str),rt=1;
for(int i=0;i<len;++i){
int c=str[i]=='1';
if(!tr[rt].to[c])tr[rt].to[c]=++allc;
rt=tr[rt].to[c];
}
if(id)tr[rt].fr|=1<<id-1,pos[cnt++]=rt,dp[1<<id-1][id-1]=len;
else tr[rt].fv=1;
}
inline void build(){
int l=0,r=0;
for(que[r++]=1;l<r;){
int u=que[l++];
for(int i=0,j,s;i<2;++i){
for(j=tr[u].g;j;j=tr[j].g)
if(tr[j].to[i])break;
if(s=tr[u].to[i]){
tr[s].g=j?tr[j].to[i]:1;
tr[s].fv|=tr[tr[s].g].fv;
que[r++]=s;
}
else tr[u].to[i]=j?tr[j].to[i]:1;
}
}
}
int dis[11][11],d[(int)6e4+5];
inline void clear(){
for(int i=1;i<=allc;++i)
tr[i].to[0]=tr[i].to[1]=tr[i].g=tr[i].fr=tr[i].fv=0;
allc=1,cnt=0;
memset(dp,-1,sizeof(dp));
memset(dis,-1,sizeof(dis));
}
inline void bfs(int u){
memset(d,-1,sizeof(d));
int l=0,r=d[pos[u]]=0;
for(que[r++]=pos[u];l<r;){
int v=que[l++];
for(int i=0;i<2;++i){
if(~d[tr[v].to[i]]||tr[tr[v].to[i]].fv)continue;
d[tr[v].to[i]]=d[v]+1;
que[r++]=tr[v].to[i];
}
}
for(int j=1;j<=allc;++j)
for(int i=0;i<cnt;++i)
if(tr[j].fr&1<<i&&~d[j])Min(dis[u][i],d[j]);
}
inline void gao(){
clear();
for(int i=1;i<=n;++i)
scanf("%s",str),Insert(i);
for(int i=1;i<=m;++i)
scanf("%s",str),Insert(0);
build();
for(int i=0;i<cnt;++i)
bfs(i);
for(int i=0;i<1<<cnt;++i){
for(int j=0;j<cnt;++j){
if(dp[i][j]==-1)continue;
for(int k=0;k<cnt;++k){
if(dis[j][k]==-1)continue;
Min(dp[i|1<<k][k],dp[i][j]+dis[j][k]);
}
}
}
int res=-1;
for(int i=0;i<cnt;++i)
if(~dp[(1<<cnt)-1][i])Min(res,dp[(1<<cnt)-1][i]);
cout<<res<<endl;
}
int main(){
for(;cin>>n>>m,n|m;)gao();
return 0;
}