-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmain.cpp
96 lines (90 loc) · 2.1 KB
/
main.cpp
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
#include <bits/stdc++.h>
using namespace std;
size_t const ALPHABET = 26;
class vertex {
public:
bool is_term;
vector<int> edges;
int sufflink;
vector<int> ids;
vertex() : is_term(false), edges(ALPHABET, -1), sufflink(-1), ids() {}
};
void add(vector<vertex> &tree, string &s, int &id) {
int cur = 0;
for (auto i : s) {
int c = static_cast<int>(i - 'a');
if (tree[cur].edges[c] == -1) {
tree[cur].edges[c] = tree.size();
cur = tree.size();
tree.emplace_back();
} else {
cur = tree[cur].edges[c];
}
}
tree[cur].ids.emplace_back(id);
tree[cur].is_term = true;
}
void create_sufflinks(vector<vertex> &tree) {
tree.emplace_back();
tree[0].sufflink = static_cast<int>(tree.size()) - 1;
for (size_t i = 0; i < ALPHABET; i++) {
tree.back().edges[i] = 0;
}
queue<size_t> q;
q.push(0);
while (!q.empty()) {
size_t cur = q.front();
q.pop();
for (size_t i = 0; i < ALPHABET; i++) {
if (tree[cur].edges[i] == -1) {
tree[cur].edges[i] = tree[tree[cur].sufflink].edges[i];
} else {
q.push(tree[cur].edges[i]);
tree[tree[cur].edges[i]].sufflink = tree[tree[cur].sufflink].edges[i];
}
}
}
}
int main() {
ifstream fin("search4.in");
ofstream fout("search4.out");
vector<vertex> tree(1);
vector<string> strings;
int k;
fin >> k;
strings.resize(k);
for (int i = 0; i < k; i++) {
fin >> strings[i];
add(tree, strings[i], i);
}
create_sufflinks(tree);
string text;
fin >> text;
vector<int> ans(k, 0);
int cur = 0;
for (auto c : text) {
int ch = c - 'a';
cur = tree[cur].edges[ch];
int find_vertex = cur;
while (find_vertex != 0 && tree[find_vertex].sufflink != -1) {
if (tree[find_vertex].is_term) {
for (auto answers : tree[find_vertex].ids) {
ans[answers] = 1;
}
}
int tmp = find_vertex;
find_vertex = tree[find_vertex].sufflink;
tree[tmp].sufflink = -1;
}
}
for (auto c : ans) {
if (c == 1) {
fout << "YES\n";
} else {
fout << "NO\n";
}
}
fin.close();
fout.close();
return 0;
}