题意：给出n个资源，m个病毒，将资源串拼接成一个串，必须包含所有的资源串，可以重叠，但是不能包含病毒，问最小的长度为多少
题解：所有串建AC自动机。对以资源串结尾的结点跑bfs，求出到其他资源串结尾的最小距离。当前结点的fail结点不能入队列，因为当前结点读下一个字符可能会遇到禁止字符串，而fail结点读相同字符可能没有遇到禁止字符串...所以每次直接将nex的可行结点入队列。(fail结点不入队列，直接设为与当前结点距离为0应该也是可行的，然而WA了)很多时候我都开始质疑数据问题了...
如果当前字符串本身包含另一个资源串，那距离不应当是0吗？有一种解释是dp的时候经过 | 操作就可以了。
#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define st first
#define nd second
#define mp make_pair
#define pii pair<int, int>
#define gg puts("gg");
#define local
//#define out1
using namespace std;
const int N = 6e4+;
const int inf = 0x3f3f3f3f;
int id(char c){
return c == '';
}
struct Tire{
int nex[N][], fail[N],end[N];
int root, L;
int node[], tot;
int newnode(){
nex[L][] = nex[L][] = -;
end[L] = ;
return L++;
}
void init(){
L = tot = ;
root = newnode();
}
void insert(char* s, int tag){
int now = root;
for(int i = ; s[i]; i++){
int p = id(s[i]);
if(nex[now][p] == -)
nex[now][p] = newnode();
now = nex[now][p];
}
if(tag >= )
end[now] |= <<tag;
else end[now] = -;
}
void build(){
queue<int> Q;
fail[root] = root;
for(int i = ; i < ; i++){
int& u = nex[root][i];
if(u == -)
u = root;
else{
fail[u] = root;
Q.push(u);
}
}
while(!Q.empty()){
int now = Q.front();
Q.pop();
for(int i = ; i < ; i++){
int& u = nex[now][i];
if(u == -)
u = nex[ fail[now] ][i];
else{
fail[u] = nex[ fail[now] ][i];
end[u] |= end[ fail[u] ];
Q.push(u);
}
}
}
}
};
Tire ac;
char s[N];
void gmin(int& a, int b){
if(a > b) a = b;
}
int dis[N], ve[N], tot;
int w[][]; void bfs(int node, int i){
memset(dis, 0x3f, sizeof(dis));
queue<int> Q;
Q.push(node); dis[node] = ;
int s = ; #ifdef out1
int j = node;
while(ac.fail[j] != ac.root){
j = ac.fail[j];
dis[j] = ;
}
dis[j] = ;
#endif while(!Q.empty()){
int sz = Q.size();
s++;
while(sz--){
int f = Q.front(); Q.pop();
for(int j = ; j < ; j++){
int to = ac.nex[f][j];
if(dis[to] < inf||ac.end[to] < ) continue ;
Q.push(to);
dis[to] = s; #ifdef out1
while(ac.fail[to] != ac.root&&dis[ac.fail[to]] == inf){
to = ac.fail[to];
dis[to] = s;
}
#endif
}
}
}
for(int j = ; j < tot; j++)
w[i][j] = dis[ ve[j] ];
}
int dp[][<<];
int main(){
#ifdef locl
freopen("in", "r", stdin);
#ifdef out1
freopen("out1", "w", stdout);
#else
freopen("out2", "w", stdout);
#endif // out1
#endif // locl
int n, m, t, ca = ;
while(~scanf("%d%d", &n, &m), n+m){
ac.init(); memset(w, 0x3f, sizeof(w));
for(int i = ; i < n; i++){
w[i][i] = ;
scanf("%s", s);
ac.insert(s, i);
}
for(int i = ; i < m; i++){
scanf("%s", s);
ac.insert(s, -);
}
ac.build(); tot = ;
for(int i = ; i < ac.L; i++)
if(!i||ac.end[i] > ) ve[tot++] = i;
memset(w, 0x3f, sizeof(w));
for(int i = ; i < tot; i++)
bfs(ve[i], i);
// for(int i = 0; i < tot; i++){
// for(int j = 0; j < tot; j++)
// printf("%10d ", w[i][j]);
// puts("");
// } memset(dp, 0x3f, sizeof(dp));
for(int i = ; i < tot; i++)
dp[i][ ac.end[ve[i]] ] = w[][i];
for(int i = ; i < (<<n); i++){
for(int j = ; j < tot; j++){
if( dp[j][i] < 0x3f3f3f3f ) for(int k = ; k < tot; k++)
if(j != k&&w[j][k] < 0x3f3f3f3f)
gmin(dp[k][i|ac.end[ve[k]]], dp[j][i]+w[j][k]);
}
} // for(int i = 0; i < n; i++)
// for(int j = 0; j < (1<<n); j++)
// printf("%d %d: %d\n", i, j, dp[i][j]); int ans = inf;
for(int i = ; i < tot; i++)
ans = min(ans, dp[i][ (<<n)- ]);
printf("%d\n", ans);
}
return ;
}
/*
2 2
1110
0111
101
1001 3 3
0001000
00100
010
11
111
1111
*/