題目大意:
給出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
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
