题意：目标串n( <= 10)个，病毒串m( < 1000)个，问包含所有目标串无病毒串的最小长度
思路：貌似是个简单的状压DP + AC自动机，但是发现dp[1 << n][5e4]根本开不出那么多空间，似乎GG。但是我们仔细想一下就能发现，既然要包含所有目标串的最小长度，那必然这个串就是只有目标串叠加组成的，只是在叠加的过程中我们不能混入病毒串。所以其实Trie树上有用的点最多就10个，我们只要处理出所有目标串之间“最小有效转化”就行了，那么空间为dp[1 << n][10]。
处理目标串之间“最小有效转化”可以直接暴力BFS，build标记后在Trie树上跑。
代码：
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 6e4 + 5;
const int M = 50 + 5;
const ull seed = 131;
const int INF = 0x3f3f3f3f;
const int MOD = 20090717;
int n, m;
int dp[1 << 10 + 5][20];
int point[1015];
int length[1015];
int dis[20][20];
int vis[maxn];
int tot;
struct Node{
int u, step;
};
struct Aho{
struct state{
int next[2];
int fail, cnt, is;
}node[maxn];
int size;
queue<int> q; void init(){
size = 0;
newtrie();
while(!q.empty()) q.pop();
} int newtrie(){
memset(node[size].next, 0, sizeof(node[size].next));
node[size].cnt = node[size].fail = 0;
return size++;
} void insert(char *s, int id){
int len = strlen(s);
int now = 0;
for(int i = 0; i < len; i++){
int c = s[i] - '0';
if(node[now].next[c] == 0){
node[now].next[c] = newtrie();
}
now = node[now].next[c];
}
node[now].cnt = 1 << id;
node[now].is = tot;
length[tot] = len;
point[tot++] = now; } void build(){
node[0].fail = -1;
q.push(0); while(!q.empty()){
int u = q.front();
q.pop();
if(node[node[u].fail].cnt && u) node[u].cnt |= node[node[u].fail].cnt;
for(int i = 0; i < 2; i++){
if(!node[u].next[i]){
if(u == 0)
node[u].next[i] = 0;
else
node[u].next[i] = node[node[u].fail].next[i];
}
else{
if(u == 0) node[node[u].next[i]].fail = 0;
else{
int v = node[u].fail;
while(v != -1){
if(node[v].next[i]){
node[node[u].next[i]].fail = node[v].next[i];
break;
}
v = node[v].fail;
}
if(v == -1) node[node[u].next[i]].fail = 0;
}
q.push(node[u].next[i]);
}
}
}
} void bfs(int x){
queue<Node> Q;
while(!Q.empty()) Q.pop();
memset(vis, 0, sizeof(vis));
dis[x][x] = 0;
vis[point[x]] = 1;
Node a, b;
a.u = point[x], a.step = 0;
Q.push(a);
while(!Q.empty()){
a = Q.front();
Q.pop();
for(int i = 0; i < 2; i++){
int v = node[a.u].next[i];
if(vis[v]) continue;
vis[v] = 1;
if(node[v].cnt < (1 << 20)){
if(node[v].cnt) dis[x][node[v].is] = a.step + 1;
b.u = v, b.step = a.step + 1;
Q.push(b);
}
}
}
} void query(){
for(int i = 0; i < (1 << n); i++)
for(int j = 0; j < n; j++)
dp[i][j] = INF;
for(int i = 0; i < n; i++){
dp[node[point[i]].cnt][i] = length[i];
}
for(int i = 0; i < (1 << n); i++){
for(int j = 0; j < n; j++){
if(dp[i][j] == INF) continue;
for(int k = 0; k < n; k++){
int arr = node[point[k]].cnt;
// if(arr & i) continue;
dp[i | arr][k] = min(dp[i | arr][k], dp[i][j] + dis[j][k]);
}
}
}
int ans = INF;
for(int i = 0; i < n; i++){
ans = min(ans, dp[(1 << n) - 1][i]);
}
printf("%d\n", ans);
} }ac;
char s[1005];
int main(){
int ca = 1;
while(~scanf("%d%d", &n, &m) && n + m){
tot = 0;
ac.init();
for(int i = 0; i < n; i++){
scanf("%s", s);
ac.insert(s, i);
}
for(int i = 0; i < m; i++){
scanf("%s", s);
ac.insert(s, 20);
}
ac.build();
for(int i = 0; i < n; i++)
ac.bfs(i);
ac.query();
}
return 0;
}
/*
2 1
1110
0111
101
1 1
1
0 */