2 2 1110 0111 101 1001 0 0
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;
}
原文：http://blog.csdn.net/xianxingwuguan1/article/details/18941079