Resource Archiver
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 100000/100000 K (Java/Others)Total Submission(s): 1429 Accepted Submission(s): 418
Problem Description
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.
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.
Input
There will be at most 10 test cases, each begins with two integers in a single line: n and m (2 <= n <= 10, 1 <= m <= 1000). The next n lines contain the resources, one in each line. The next m lines contain the virus codes, one in
each line. The resources and virus codes are all non-empty 01 strings without spaces inside. Each resource is at most 1000 characters long. The total length of all virus codes is at most 50000. The input ends with n = m = 0.
Output
For each test case, print the length of shortest string.
Sample Input
2 2 1110 0111 101 1001 0 0
Sample Output
5
题意：给定n个子串，m个病毒串，然后让合并，使得串尽可能的短，但是不能含有病毒串，
这个题好难，n不超过10，看了别人的思路,先把子串与病毒串插进ac自动机去，子串标记为对应的状态，病毒串末尾标记为-1，然后把合法的子串节点取出来，然后通过bfs求两两之间的
最短路，然后状态压缩dp。
代码：
/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-5 17:31:21
File Name :4.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
struct node{
int next[60010][2],end[60010],fail[60030];
int root,L;
int newnode(){
next[L][0]=next[L][1]=-1;
end[L++]=0;
return L-1;
}
void init(){
L=0;
root=newnode();
}
void insert(char *str,int id){
int len=strlen(str);
int now=root;
for(int i=0;i<len;i++){
int p=str[i]-‘0‘;
if(next[now][p]==-1)
next[now][p]=newnode();
now=next[now][p];
}
if(id==-1)
end[now]=-1;
else end[now]|=(1<<id);
}
void build(){
queue<int> q;
fail[root]=root;
for(int i=0;i<2;i++){
if(next[root][i]==-1)
next[root][i]=root;
else {
fail[next[root][i]]=root;
q.push(next[root][i]);
}
}
while(!q.empty()){
int now=q.front();q.pop();
if(end[fail[now]]==-1)end[now]=-1;
else end[now]|=end[fail[now]];
for(int i=0;i<2;i++){
if(next[now][i]==-1)
next[now][i]=next[fail[now]][i];
else {
fail[next[now][i]]=next[fail[now]][i];
q.push(next[now][i]);
}
}
}
}
int dp[1<<10][60],dis[60][60],pnt[100],cnt,que[100010],dist[100000];
void bfs(int s){
for(int i=0;i<L;i++)
dist[i]=INF;
dist[pnt[s]]=0;
int front=0,rear=0;
que[rear++]=pnt[s];
while(front<rear){
int now=que[front++];
for(int i=0;i<2;i++){
int u=next[now][i];
if(end[u]==-1||dist[u]!=INF)
continue;
dist[u]=dist[now]+1;
que[rear++]=u;
}
}
for(int i=0;i<cnt;i++)dis[s][i]=dist[pnt[i]];
}
void F1(int n){
cnt=0;
for(int i=0;i<L;i++)
if(i==0||end[i]>0)
pnt[cnt++]=i;
// cout<<"haha:"<<L<<" "<<cnt<<endl;
for(int i=0;i<cnt;i++)bfs(i);
for(int i=0;i<(1<<n);i++)
for(int j=0;j<cnt;j++)
dp[i][j]=INF;
dp[0][0]=0;
for(int i=0;i<(1<<n);i++)
for(int j=0;j<cnt;j++){
if(dp[i][j]==INF)continue;
for(int k=0;k<cnt;k++)
dp[i|end[pnt[k]]][k]=min(dp[i|end[pnt[k]]][k],dp[i][j]+dis[j][k]);
}
int ans=INF;
for(int i=0;i<cnt;i++)
ans=min(ans,dp[(1<<n)-1][i]);
cout<<ans<<endl;
}
}ac;
char str[10030];
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int i,j,k,m,n;
while(~scanf("%d%d",&n,&m)){
if(n==0&&m==0)break;
ac.init();
for(i=0;i<n;i++){
scanf("%s",str);
ac.insert(str,i);
}
while(m--){
scanf("%s",str);
ac.insert(str,-1);
}
ac.build();
ac.F1(n);
}
return 0;
}