最近一直在刷AC自动机，感觉每天脑子都被tire图充斥着。。。。。 orz今天看到的一个题目，感觉A完后自己还是挺有成就感的。
题目编号为hdu3247，描述为如下：
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.
Output
For each test case, print the length of shortest string.
但细细一想，发现问题来了。。。。。 题目说有50000个点，即自动机上有50000个点或状态，每个状态可能含有的子串情况为2^n<=1024种，于是50000*1024 ORZ TML+MLT
虽然老衲自己想到了用二进制压位，但是显然对于这个题目来说始终是杯水车薪，照超。咋办？
于是我在网上搜了一下题解，看到了一位不知名的神犇的题解，好像瞬间明白了什么。。。。。
仔细一看题，需要包含的子串最多只有10个，并且要构造一个字符串并且要求它最短，肯定就是刚刚好构造完第n个（最后一个）就必须停止。所以最最最最最最重要的，最最最最最最有效的一个优化就是 先bfs一遍，把每个单词结尾的节点的距离预算出来。然后再去DP。这样相当于只有10个状态的dp了，wa（语气词——而不是交上去wa了），这个题就是这样被秒了。
但是有诸多细节需要注意哦，老衲就是因为这些细节，贡献了N（N>=5)次wa T_T
不多说了，直接上代码把。。。。。
＃i nclude <iostream>
＃i nclude <cstdio>
＃i nclude <cstring>
＃i nclude <queue>
#define maxn 66666
using namespace std;
int next[maxn][2],f[14][1500],fail[maxn],tag[maxn],dis[22][22],G[22],d[maxn];
int n,m,N,t,ans;
char s[2111];
void insert(int id)
{
int cur=0,tep;
for (int i=0; s[i]; i++)
{
tep=s[i]-'0';
if (next[cur][tep]==0)
next[cur][tep]=++N;
cur=next[cur][tep];
}
if (id==-1)
{
tag[cur]=-1;
return ;
}
if (tag[cur]!=-1)
{
tag[cur]|=1<<(id-1);
G[id]=cur;
}
else G[id]=-1;
}
void buildAC()
{
queue<int> Q;
Q.push(0);
int cur,child;
while (!Q.empty())
{
cur=Q.front();
Q.pop();
for (int i=0; i<2; i++)
{
child=next[cur][i];
if (child)
{
Q.push(child);
if (cur==0) fail[child]=0;
else
{
fail[child]=next[fail[cur]][i];
if (tag[fail[child]]==-1) tag[child]=-1;
else tag[child]|=tag[fail[child]];
}
}
else next[cur][i]=next[fail[cur]][i];
}
}
}
void bfs(int k)
{
if (tag[G[k]]==-1) return;
memset(d,-1,sizeof d);
queue<int> Q;
int cur,tep;
Q.push(G[k]);
d[G[k]]=0;
while (!Q.empty())
{
cur=Q.front();
Q.pop();
for (int i=0; i<2; i++)
{
tep=next[cur][i];
if (tag[tep]==-1) continue;
if (d[tep]==-1)
{
d[tep]=d[cur]+1;
Q.push(tep);
}
}
}
for (int i=1; i<=n; i++)
if (G[i]>0) dis[k][i]=d[G[i]];
}
int main()
{
while (scanf("%d%d",&n,&m) && (n|m))
{
N=0;
memset(next,0,sizeof next);
memset(fail,0,sizeof fail);
memset(tag,0,sizeof tag);
for (int i=1; i<=n; i++)
{
scanf("%s",s);
insert(i);
}
for (int i=1; i<=m; i++)
{
scanf("%s",s);
insert(-1);
}
buildAC();
memset(dis,-1,sizeof dis);
for (int i=0; i<=n; i++) if (G[i]>=0) bfs(i);
memset(f,0x7f,sizeof f);
f[0][0]=0;
for (int i=0; i<(1<<n); i++)
{
for (int j=0; j<=n; j++)
{
if (G[j]==-1 || f[j][i]==-1) continue;
for (int k=0; k<=n; k++)
{
if (G[k]==-1 || k==j || dis[j][k]<0) continue;
t=i|tag[G[k]];
if (f[k][t]>0) f[k][t]=min(f[k][t],f[j][i]+dis[j][k]);
else f[k][t]=f[j][i]+dis[j][k];
}
}
}
ans=~0U>>1; t=(1<<n)-1;
for (int i=0; i<=n; i++)
if (f[i][t]<ans) ans=f[i][t];
printf("%d\n",ans);
}
return 0;
}
（注：本人代码风格略丑，求不喷）
