题目，求最短的包含所有n个DNA片段且不包含任何一个病毒片段的序列。
容易用所有DNA片段和病毒片段建一个AC自动机，构造fail时处理一下各个结点后缀是DNA或者病毒的情况，然后dp[S][u]表示包含DNA片段的集合是S的且后缀状态是自动机第u个结点的最短序列长度，然后顺着AC自动机避开病毒串转移。
不过构建的AC自动机结点上限60000左右，集合有1024个状态，这样内存开不下。看了题解，原来不必要考虑自动机所有结点——
- dp[S][u]表示包含DNA片段集合是S且后缀是第u个DNA片段的最短序列长度
- 通过BFS预处理出各个DNA片段到其他DNA片段在AC自动机上的距离，要注意某些DNA片段的后缀包含其他DNA片段的情况，还有跳过后缀包含病毒串的结点。
- 转移就是dp[S][u]=max(dp[S-{u}][v]+dist[v][u])（v∈S-{u}）
这个解法的正确性我还得消化消化。。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define INF (1<<29)
#define MAXN 66666
int tn,ch[MAXN][],fail[MAXN],flag[MAXN];
int idx[];
void insert(char *s,int k){
int x=;
for(int i=; s[i]; ++i){
int y=s[i]-'';
if(ch[x][y]==) ch[x][y]=++tn;
x=ch[x][y];
}
if(k==- || flag[x]==-) flag[x]=-;
else{
idx[k]=x;
flag[x]|=(<<k);
}
}
int que[MAXN],front,rear;
void getfail(){
memset(fail,,sizeof(fail));
front=rear=;
if(ch[][]) que[rear++]=ch[][];
if(ch[][]) que[rear++]=ch[][];
while(front<rear){
int x=que[front++];
for(int i=; i<; ++i){
if(ch[x][i]){
que[rear++]=ch[x][i];
fail[ch[x][i]]=ch[fail[x]][i];
if(flag[ch[x][i]]==- || flag[ch[fail[x]][i]]==-) flag[ch[x][i]]=-;
else flag[ch[x][i]]|=flag[ch[fail[x]][i]];
}else ch[x][i]=ch[fail[x]][i];
}
}
} int n,m,dist[MAXN],G[][];
void BFS(int k){
memset(dist,,sizeof(dist));
dist[idx[k]]=;
front=rear=;
que[rear++]=idx[k];
while(front<rear){
int x=que[front++];
if(flag[x]){
for(int i=; i<n; ++i){
if(((flag[x]>>i)&)==) continue;
G[k][i]=min(G[k][i],dist[x]-);
}
}
for(int i=; i<; ++i){
int y=ch[x][i];
if(flag[y]==- || dist[y]) continue;
dist[y]=dist[x]+;
que[rear++]=y;
}
}
}
int d[<<][],len[];
int main(){
char str[];
while(~scanf("%d%d",&n,&m) && (n||m)){
tn=;
memset(ch,,sizeof(ch));
memset(flag,,sizeof(flag));
for(int i=; i<n; ++i){
scanf("%s",str);
insert(str,i);
len[i]=strlen(str);
}
for(int i=; i<m; ++i){
scanf("%s",str);
insert(str,-);
}
getfail();
for(int i=; i<n; ++i){
for(int j=; j<n; ++j) G[i][j]=INF;
}
for(int i=; i<n; ++i){
BFS(i);
}
for(int i=; i<(<<n); ++i){
for(int j=; j<n; ++j) d[i][j]=INF;
}
for(int i=; i<n; ++i){
d[<<i][i]=len[i];
}
for(int i=; i<(<<n); ++i){
for(int j=; j<n; ++j){
if(((i>>j)&)==) continue;
for(int k=; k<n; ++k){
if(((i>>k)&)== || j==k) continue;
d[i][j]=min(d[i][j],d[i^(<<j)][k]+G[k][j]);
}
}
}
int res=INF;
for(int i=; i<n; ++i) res=min(res,d[(<<n)-][i]);
printf("%d\n",res);
}
return ;
}