#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
int ans[MAXN];
vector<int> queries[MAXN];
int n, m;
map<char, int> conv({{'A', 0}, {'U', 1}, {'G', 2}, {'C', 3}});
class Trie {
public:
Trie *nxt[4];
int sz;
Trie *rev_t;
int term = 0; // num ending at this position
vector<int> rev_queries;
vector<int> seq;
Trie() {
sz = 0;
for (int i = 0; i < 4; i++) nxt[i] = nullptr;
}
void merge(Trie *oth) {
sz += oth->sz;
for (int i = 0; i < 4; i++) {
if (nxt[i] == nullptr) nxt[i] = oth->nxt[i];
else if (oth->nxt[i] != nullptr) nxt[i]->merge(oth->nxt[i]);
}
// delete oth;
}
void ins(vector<int> &s, int p = 0, int num = 1) {
sz += num;
if (p == s.size()) {
term += num;
seq = s;
return;
}
if (nxt[s[p]] == nullptr) nxt[s[p]] = new Trie();
nxt[s[p]]->ins(s, p+1, num);
}
void ins_query(vector<int> &f, int p, int id) {
if (p == f.size()) rev_queries.push_back(id);
else {
if (nxt[f[p]] != nullptr) nxt[f[p]]->ins_query(f, p+1, id);
}
}
void dfs() {
for (int i = 0; i < 4; i++) if (nxt[i] != nullptr) nxt[i]->dfs();
rev_t = new Trie();
if (term) {
reverse(seq.begin(), seq.end());
rev_t->ins(seq, 0, term);
}
for (int i = 0; i < 4; i++) if (nxt[i] != nullptr) rev_t->merge(nxt[i]->rev_t);
for (int v: rev_queries) {
reverse(queries[v].begin(), queries[v].end());
ans[v] = rev_t->count(queries[v]);
}
}
int count(vector<int> &v, int p = 0) {
if (p == v.size()) return sz;
if (nxt[v[p]] == nullptr) return 0;
return nxt[v[p]]->count(v, p+1);
}
};
Trie *tree;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> m;
tree = new Trie();
for (int i = 0; i < n; i++) {
string s; cin >> s;
vector<int> v;
for (int j = 0; j < s.size(); j++) v.push_back(conv[s[j]]);
tree->ins(v);
}
for (int i = 0; i < m; i++) {
string s1, s2; cin >> s1 >> s2;
vector<int> v1;
for (int j = 0; j < s1.size(); j++) v1.push_back(conv[s1[j]]);
for (int j = 0; j < s2.size(); j++) queries[i].push_back(conv[s2[j]]);
tree->ins_query(v1, 0, i);
}
tree->dfs();
for (int i = 0; i < m; i++) cout << ans[i] << "\n";
}
Compilation message
selling_rna.cpp: In member function 'void Trie::ins(std::vector<int>&, int, int)':
selling_rna.cpp:33:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | if (p == s.size()) {
| ~~^~~~~~~~~~~
selling_rna.cpp: In member function 'void Trie::ins_query(std::vector<int>&, int, int)':
selling_rna.cpp:42:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | if (p == f.size()) rev_queries.push_back(id);
| ~~^~~~~~~~~~~
selling_rna.cpp: In member function 'int Trie::count(std::vector<int>&, int)':
selling_rna.cpp:61:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | if (p == v.size()) return sz;
| ~~^~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int j = 0; j < s.size(); j++) v.push_back(conv[s[j]]);
| ~~^~~~~~~~~~
selling_rna.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int j = 0; j < s1.size(); j++) v1.push_back(conv[s1[j]]);
| ~~^~~~~~~~~~~
selling_rna.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int j = 0; j < s2.size(); j++) queries[i].push_back(conv[s2[j]]);
| ~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2680 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2684 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
197 ms |
240300 KB |
Output is correct |
2 |
Correct |
193 ms |
229308 KB |
Output is correct |
3 |
Correct |
577 ms |
671136 KB |
Output is correct |
4 |
Correct |
542 ms |
640036 KB |
Output is correct |
5 |
Correct |
343 ms |
421452 KB |
Output is correct |
6 |
Correct |
341 ms |
427800 KB |
Output is correct |
7 |
Correct |
199 ms |
195884 KB |
Output is correct |
8 |
Correct |
349 ms |
403500 KB |
Output is correct |
9 |
Correct |
301 ms |
350540 KB |
Output is correct |
10 |
Correct |
219 ms |
276464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
5324 KB |
Output is correct |
2 |
Correct |
21 ms |
5320 KB |
Output is correct |
3 |
Correct |
25 ms |
5436 KB |
Output is correct |
4 |
Correct |
23 ms |
4536 KB |
Output is correct |
5 |
Correct |
24 ms |
6264 KB |
Output is correct |
6 |
Correct |
26 ms |
5832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2680 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2684 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2740 KB |
Output is correct |
8 |
Correct |
197 ms |
240300 KB |
Output is correct |
9 |
Correct |
193 ms |
229308 KB |
Output is correct |
10 |
Correct |
577 ms |
671136 KB |
Output is correct |
11 |
Correct |
542 ms |
640036 KB |
Output is correct |
12 |
Correct |
343 ms |
421452 KB |
Output is correct |
13 |
Correct |
341 ms |
427800 KB |
Output is correct |
14 |
Correct |
199 ms |
195884 KB |
Output is correct |
15 |
Correct |
349 ms |
403500 KB |
Output is correct |
16 |
Correct |
301 ms |
350540 KB |
Output is correct |
17 |
Correct |
219 ms |
276464 KB |
Output is correct |
18 |
Correct |
26 ms |
5324 KB |
Output is correct |
19 |
Correct |
21 ms |
5320 KB |
Output is correct |
20 |
Correct |
25 ms |
5436 KB |
Output is correct |
21 |
Correct |
23 ms |
4536 KB |
Output is correct |
22 |
Correct |
24 ms |
6264 KB |
Output is correct |
23 |
Correct |
26 ms |
5832 KB |
Output is correct |
24 |
Correct |
177 ms |
201432 KB |
Output is correct |
25 |
Correct |
197 ms |
202868 KB |
Output is correct |
26 |
Correct |
175 ms |
198640 KB |
Output is correct |
27 |
Correct |
457 ms |
553392 KB |
Output is correct |
28 |
Correct |
133 ms |
39884 KB |
Output is correct |
29 |
Correct |
105 ms |
15096 KB |
Output is correct |