题目大意:
给出N个带通配符(?和*)的模式串, M个询问, 询问一个给你的字符串能匹配哪些模式串. 模式串长度不超过6, 询问串长度不超过20.
简要分析:
带通配符AC自动机? 不是的, 看字符串的长度都那么小, 暴力一下就可以了. 把所有模式串丢到Trie里面, *和?也作为一种转移, 对于每个询问串, 暴力dfs就可以了.
代码实现:
View Code
1
#include <cstdio>
2
#include <cstdlib>
3
#include <cstring>
4
#include <vector>
5
#include <algorithm>
6
using
namespace
std;
7
8
const
int
MAX_N =
100000
, MAX_M =
100
, P_LEN =
6
, W_LEN =
20
;
9
int
n, m;
10
char
p[P_LEN +
1
], w[W_LEN +
1
];
11
12
#define
pb push_back
13
14
namespace
trie {
15
const
int
MAX_NODE =
200000
, SON =
28
;
16
17
struct
node_t {
18
vector <
int
> v;
19
node_t *son[SON];
20
node_t() { v.clear(), memset(son,
0
,
sizeof
(son)); }
21
} node_pool[MAX_NODE +
1
], *node_idx = node_pool, *root = NULL;
22
23
node_t *node_alloc() {
24
return
node_idx ++;
25
}
26
27
void
init() {
28
root = node_alloc();
29
}
30
31
void
ins(
int
id,
char
*str) {
32
node_t *pos = root;
33
while
(*str) {
34
int
t = *(str ++);
35
t = (t ==
'
?
'
?
26
: (t ==
'
*
'
?
27
: t -
'
a
'
));
36
if
(!pos -> son[t]) pos -> son[t] = node_alloc();
37
pos = pos -> son[t];
38
}
39
pos -> v.pb(id);
40
}
41
42
vector <
int
> ans;
43
int
sz;
44
45
void
dfs(
char
*str, node_t *pos,
int
idx) {
46
if
(str[idx] !=
0
) {
47
int
t = str[idx] -
'
a
'
;
48
if
(pos -> son[t]) dfs(str, pos -> son[t], idx +
1
);
49
if
(pos -> son[
26
]) dfs(str, pos -> son[
26
], idx +
1
);
50
if
(pos -> son[
27
])
51
for
(
int
i = idx; i <= sz; i ++) dfs(str, pos -> son[
27
], i);
52
}
53
else
{
54
for
(
int
i =
0
, rb = pos -> v.size(); i < rb; i ++) ans.pb(pos -> v[i]);
55
if
(pos -> son[
27
]) dfs(str, pos -> son[
27
], idx);
56
}
57
}
58
59
void
go(
char
*str) {
60
ans.clear();
61
sz = strlen(str);
62
dfs(str, root,
0
);
63
sort(ans.begin(), ans.end());
64
ans.resize(distance(ans.begin(), unique(ans.begin(), ans.end())));
65
if
(!ans.size()) printf(
"
Not match\n
"
);
66
else
{
67
for
(
int
i =
0
, rb = ans.size(); i < rb; i ++) printf(
"
%d
"
, ans[i]);
68
printf(
"
\n
"
);
69
}
70
}
71
}
72
73
int
main(){
74
scanf(
"
%d%d
"
, &n, &m);
75
trie::init();
76
for
(
int
i =
0
; i < n; i ++) {
77
scanf(
"
%s
"
, p);
78
trie::ins(i, p);
79
}
80
for
(
int
i =
0
; i < m; i ++) {
81
scanf(
"
%s
"
, w);
82
trie::go(w);
83
}
84
return
0
;
85
}
