题目大意
给定词典 (D)，词典中的单词连起来（单词间分割开来）为文章。求每个单词在文章中的出现次数。
(1 leqslant |D| leqslant 200)
(1 leqslant |T| leqslant 1,000,000)
题目链接
BZOJ 3172
CodeVS 2542
题解
AC 自动机模版题。
单词间用字符集外的字符连接。
代码
为了让儿子数少点，<code> 是ASCII中a` 的前一个。。。
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
|
#include <cstring>
#include <queue>
const int MAXN = 205;
const int MAXLEN = 1000005;
const int CHARSET_SIZE = 'z' - ''</span> + <span class="number">1</span>;</span><br/><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> BASE_CHAR = <span class="string">'';
struct {
struct Node {
Node *c[CHARSET_SIZE], *fail, *next;
bool isWord;
int ans;
Node(bool isWord = false) : isWord(isWord), fail(NULL), next(NULL), ans(0) {
for (int i = 0; i < CHARSET_SIZE; i++) c[i] = NULL;
}
void apply() {
ans++;
if (next) next->apply();
}
} *root;
Trie() : root(NULL) {}
Node *insert(char *begin, char *end) {
Node **u = &root;
for (char *p = begin; p != end; p++) {
if (!(*u)) *u = new Node();
u = &(*u)->c[*p];
}
if (!(*u)) *u = new Node(true);
else (*u)->isWord = true;
return *u;
}
void build() {
std::queue<Node *> q;
q.push(root);
root->fail = root;
root->next = NULL;
while (!q.empty()) {
Node *u = q.front();
q.pop();
for (int i = 0; i < CHARSET_SIZE; i++) {
Node *c = u->c[i];
if (!c) continue;
Node *v = u->fail;
while (v != root && !v->c[i]) v = v->fail;
c->fail = u != root && v->c[i] ? v->c[i] : root;
c->next = c->fail->isWord ? c->fail : c->fail->next;
q.push(c);
}
}
}
void exec(char *begin, char *end) {
Node *u = root;
for (char *p = begin; p != end; p++) {
while (u != root && !u->c[*p]) u = u->fail;
u = u->c[*p] ? u->c[*p] : root;
if (u->isWord) u->apply();
else if (u->next) u->next->apply();
}
}
} t;
int main() {
int n;
scanf("%d", &n);
static Trie::Node *words[MAXN];
static char str[MAXLEN + MAXN];
char *p = str;
for (int i = 0; i < n; i++) {
static char s[MAXLEN];
scanf("%s", s);
int len = strlen(s);
for (int i = 0; i < len; i++) s[i] -= BASE_CHAR, *p++ = s[i];
words[i] = t.insert(s, s + len);
*p++ = 0;
}
*--p = 0;
t.build();
t.exec(str, p);
for (int i = 0; i < n; i++) printf("%dn", words[i]->ans);
return 0;
}
|
近期评论