Great! Your new software is almost finished! The only thing left to do is archiving all your n resource files into a big one. 
Wait a minute… you realized that it isn’t as easy as you thought. Think about the virus killers. They’ll find your software suspicious, if your software contains one of the m predefined virus codes. You absolutely don’t want this to happen. 
Technically, resource files and virus codes are merely 01 strings. You’ve already convinced yourself that none of the resource strings contain a virus code, but if you make the archive arbitrarily, virus codes can still be found somewhere. 
Here comes your task (formally): design a 01 string that contains all your resources (their occurrences can overlap), but none of the virus codes. To make your software smaller in size, the string should be as short as possible.

5

题目大意：给n个资源01串和m个病毒01串。构造一个最短的01串使其包含所有的资源串，但不包含任何一个病毒串。
题目分析：建立好AC自动机后，在上面广搜即可。

代码如下：

# include<iostream>
# include<cstdio>
# include<queue>
# include<cstring>
# include<algorithm>
using namespace std;

const int N=10000;

int ch[6*N+5][2];
int fail[6*N+5];
int sz,type[6*N+5];

void init()
{
	sz=0;
	memset(ch,-1,sizeof(ch));
	memset(type,0,sizeof(type));
}

int idx(char c)
{
	return c-‘0‘;
}

void insert(char *s,int val)
{
	int r=0;
	int n=strlen(s);
	for(int i=0;i<n;++i){
		int c=idx(s[i]);
		if(ch[r][c]==-1) ch[r][c]=++sz;
		r=ch[r][c];
	}
	type[r]=val;
}

void getFail()
{
	queue<int>q;
	fail[0]=0;
	for(int i=0;i<2;++i){
		if(ch[0][i]==-1)
			ch[0][i]=0;
		else{
			q.push(ch[0][i]);
			fail[ch[0][i]]=0;
		}
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		if(type[fail[u]]>0)
			type[u]|=type[fail[u]];
		for(int i=0;i<2;++i){
			if(ch[u][i]==-1)
				ch[u][i]=ch[fail[u]][i];
			else{
				fail[ch[u][i]]=ch[fail[u]][i];
				q.push(ch[u][i]);
			}
		}
	}
}

struct Node
{
	int step;
	int loca;
	int sta;
};
int n,m;
char s[1005];
char vis[6*N+5][1<<10];

int bfs()
{
	queue<Node>q;
	memset(vis,0,sizeof(vis));
	q.push(Node{0,0,0});
	while(!q.empty())
	{
		Node u=q.front();
		q.pop();
		if(u.sta==(1<<n)-1)
			return u.step;
		for(int i=0;i<2;++i) if(type[ch[u.loca][i]]>=0){
			int v=ch[u.loca][i];
			if(vis[v][u.sta|type[v]]) continue;
			vis[v][u.sta|type[v]]=1;
			q.push(Node{u.step+1,v,u.sta|type[v]});
		}
	}
	return -1;
}

int main()
{
	while(~scanf("%d%d",&n,&m)&&(n+m))
	{
		init();
		for(int i=0;i<n;++i){
			scanf("%s",s);
			insert(s,1<<i);
		}
		for(int i=0;i<m;++i){
			scanf("%s",s);
			insert(s,-1);
		}
		getFail();
		printf("%d\n",bfs());
	}
	return 0;
}