Resource Archiver(AC自动机+状压DP)

描述

传送门:HDU3247

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.

Input

There will be at most $10$ test cases, each begins with two integers in a single line: $n$ and $m$ $(2 ≤ n ≤ 10, 1 ≤ m ≤ 1000)$. The next $n$ lines contain the resources, one in each line. The next $m$ lines contain the virus codes, one in each line. The resources and virus codes are all non-empty 01 strings without spaces inside. Each resource is at most $1000$ characters long. The total length of all virus codes is at most $50000$. The input ends with $n = m = 0$.

Output

For each test case, print the length of shortest string.

Sample Input

1
2
3
4
5
6
2 2
1110
0111
101
1001
0 0

Sample Output

1
5

思路

  • 把所有的串放在一起建立AC自动机,不允许出现的串标记为-1,资源串最多10个所以考虑状态压缩。
  • $dp[i][j]$表示资源串状态集合为$i$,在自动机上$j$结点的长度。
  • 转移方程就很简单了 $dp[i | val[k]][k] = min(dp[i | val[k])][k], dp[i][j] + dis[j][k])$
  • 当然,实际上能走的结点很少,我们可以先离散化这些点来压缩空间。
  • 那么我们怎么求得$dis[j][k]$?由于我们已经建立好了AC自动机,所以我们可以对安全结点进行BFS,得到它到其他安全结点的距离。
  • 具体实现见代码慢慢体会~

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int maxn = 5e5 + 5;
struct Trie
{
int ch[maxn][2];
int val[maxn], f[maxn];
int sz, rt;
inline int newnode()
{
clr(ch[sz], -1), val[sz] = 0;
return sz++;
}
inline int idx(char c) { return c - '0'; }
void init() { sz = 0, rt = newnode(); }
void insert(const char* s, const int& id)
{
int n = strlen(s), u = rt;
for (int i = 0; i < n; i++)
{
int c = idx(s[i]);
if (ch[u][c] == -1) ch[u][c] = newnode();
u = ch[u][c];
}
val[u] |= id;
}
void build()
{
queue<int> q;
f[rt] = rt;
for (int c = 0; c < 2; c++)
{
if (~ch[rt][c])
f[ch[rt][c]] = rt, q.push(ch[rt][c]);
else
ch[rt][c] = rt;
}
while (!q.empty())
{
int u = q.front();
q.pop();
val[u] |= val[f[u]];
for (int c = 0; c < 2; c++)
{
if (~ch[u][c])
f[ch[u][c]] = ch[f[u]][c], q.push(ch[u][c]);
else
ch[u][c] = ch[f[u]][c];
}
}
}
vector<int> w;
int G[1 << 10][1 << 10];
int vis[maxn];
void bfs(int s)
{
queue<int> q;
clr(vis, -1);
vis[w[s]] = 0;
q.push(w[s]);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int c = 0; c < 2; c++)
{
int v = ch[u][c];
if (~vis[v] || val[v] == -1) continue;
vis[v] = vis[u] + 1;
q.push(v);
}
}
for (int i = 0; i < w.size(); i++) G[s][i] = vis[w[i]];
}
int dp[1 << 10][1 << 10];
int solve(int n)
{
w.clear();
clr(G, 0x3f);
clr(dp, 0x3f);
for (int i = 0; i < sz; i++)
if (i == 0 || val[i] > 0) w.pb(i);
for (int i = 0; i < w.size(); i++) bfs(i);
dp[0][0] = 0;
for (int i = 0; i < (1 << n); i++)
for (int j = 0; j < w.size(); j++)
if (dp[i][j] != INF)
for (int k = 0; k < w.size(); k++)
if (~G[j][k])
dp[i | val[w[k]]][k] = min(dp[i | val[w[k]]][k], dp[i][j] + G[j][k]);
int ans = INF;
for (int i = 0; i < w.size(); i++)
ans = min(ans, dp[(1 << n) - 1][i]);
return ans;
}
};

Trie ac;

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n, m;
char buf[1005];
while (~scanf("%d%d", &n, &m) && n + m)
{
ac.init();
for (int i = 0; i < n; i++)
{
scanf("%s", buf);
ac.insert(buf, 1 << i);
}
for (int i = 0; i < m; i++)
{
scanf("%s", buf);
ac.insert(buf, -1);
}
ac.build();
printf("%d\n", ac.solve(n));
}
return 0;
}
捐助作者
0%