#include <bits/stdc++.h>
using namespace std;
int chrToHash[256]{};
int n, m;
vector<string> str;
vector<int> results;
struct TrieNode
{
int cnt = 0;
int l = -1, r = -1;
vector<int> v;
string* ogString{};
TrieNode* children[4]{};
void depthFirstSearch(int& timer);
};
vector<TrieNode*> trieNodes;
void TrieNode::depthFirstSearch(int& timer)
{
l = timer, timer += cnt;
for (int i = 0; i < cnt; i++)
trieNodes.push_back(this);
for (auto &child : children)
{
if (child == nullptr) continue;
child->depthFirstSearch(timer);
}
r = timer;
}
struct Trie
{
TrieNode *root = new TrieNode;
void insert(string& s)
{
auto curr = root;
int size = (int)s.size();
for (int i = 0; i < size; i++)
{
int d = chrToHash[s[i]];
if (curr->children[d] == nullptr)
curr->children[d] = new TrieNode;
curr = curr->children[d];
}
curr->ogString = &s;
curr->cnt++;
}
TrieNode* getNode(const string& s)
{
auto curr = root;
int size = (int)s.size();
for (int i = 0; i < size; i++)
{
int d = chrToHash[s[i]];
if (curr->children[d] == nullptr)
return nullptr;
curr = curr->children[d];
}
return curr;
}
void process()
{
int timer = 0;
trieNodes.reserve(n);
root->depthFirstSearch(timer);
}
} trie;
struct Eirt
{
TrieNode *root = new TrieNode;
void insert(string& s, const int& index)
{
auto curr = root;
curr->v.push_back(index);
int size = (int)s.size();
for (int i = size - 1; i >= 0; i--)
{
int d = chrToHash[s[i]];
if (curr->children[d] == nullptr)
curr->children[d] = new TrieNode;
curr = curr->children[d];
curr->v.push_back(index);
}
curr->ogString = &s;
}
TrieNode* getNode(const string& s)
{
auto curr = root;
int size = (int)s.size();
for (int i = size - 1; i >= 0; i--)
{
int d = chrToHash[s[i]];
if (curr->children[d] == nullptr)
return nullptr;
curr = curr->children[d];
}
return curr;
}
} eirt;
int main()
{
// freopen("inp.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios::sync_with_stdio(false);
chrToHash['A'] = 0;
chrToHash['C'] = 1;
chrToHash['G'] = 2;
chrToHash['U'] = 3;
cin >> n >> m;
str.resize(n);
for (int i = 0; i < n; i++)
{
cin >> str[i];
trie.insert(str[i]);
}
trie.process();
for (int i = 0; i < n; i++)
eirt.insert(*trieNodes[i]->ogString, i);
results.resize(m);
string pref, suff;
for (int q = 0; q < m; q++)
{
cin >> pref >> suff;
auto itr = trie.getNode(pref);
auto jtr = eirt.getNode(suff);
if (itr == nullptr || jtr == nullptr)
{
results[q] = 0;
continue;
}
auto l = lower_bound(jtr->v.begin(), jtr->v.end(), itr->l);
auto r = lower_bound(jtr->v.begin(), jtr->v.end(), itr->r);
results[q] = r - l;
}
for (auto &result : results)
cout << result << '\n';
}
Compilation message
selling_rna.cpp: In member function 'void Trie::insert(std::string&)':
selling_rna.cpp:47:35: warning: array subscript has type 'char' [-Wchar-subscripts]
47 | int d = chrToHash[s[i]];
| ^
selling_rna.cpp: In member function 'TrieNode* Trie::getNode(const string&)':
selling_rna.cpp:62:35: warning: array subscript has type 'char' [-Wchar-subscripts]
62 | int d = chrToHash[s[i]];
| ^
selling_rna.cpp: In member function 'void Eirt::insert(std::string&, const int&)':
selling_rna.cpp:89:35: warning: array subscript has type 'char' [-Wchar-subscripts]
89 | int d = chrToHash[s[i]];
| ^
selling_rna.cpp: In member function 'TrieNode* Eirt::getNode(const string&)':
selling_rna.cpp:104:35: warning: array subscript has type 'char' [-Wchar-subscripts]
104 | int d = chrToHash[s[i]];
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
320 KB |
Output is correct |
5 |
Correct |
1 ms |
324 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
174 ms |
249864 KB |
Output is correct |
2 |
Correct |
160 ms |
236324 KB |
Output is correct |
3 |
Correct |
144 ms |
196564 KB |
Output is correct |
4 |
Correct |
139 ms |
187036 KB |
Output is correct |
5 |
Correct |
225 ms |
268588 KB |
Output is correct |
6 |
Correct |
215 ms |
272688 KB |
Output is correct |
7 |
Correct |
40 ms |
10964 KB |
Output is correct |
8 |
Correct |
192 ms |
164960 KB |
Output is correct |
9 |
Correct |
157 ms |
139344 KB |
Output is correct |
10 |
Correct |
136 ms |
135640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
3664 KB |
Output is correct |
2 |
Correct |
11 ms |
3164 KB |
Output is correct |
3 |
Correct |
14 ms |
3408 KB |
Output is correct |
4 |
Correct |
10 ms |
2824 KB |
Output is correct |
5 |
Correct |
12 ms |
3144 KB |
Output is correct |
6 |
Correct |
14 ms |
3432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
320 KB |
Output is correct |
5 |
Correct |
1 ms |
324 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
174 ms |
249864 KB |
Output is correct |
9 |
Correct |
160 ms |
236324 KB |
Output is correct |
10 |
Correct |
144 ms |
196564 KB |
Output is correct |
11 |
Correct |
139 ms |
187036 KB |
Output is correct |
12 |
Correct |
225 ms |
268588 KB |
Output is correct |
13 |
Correct |
215 ms |
272688 KB |
Output is correct |
14 |
Correct |
40 ms |
10964 KB |
Output is correct |
15 |
Correct |
192 ms |
164960 KB |
Output is correct |
16 |
Correct |
157 ms |
139344 KB |
Output is correct |
17 |
Correct |
136 ms |
135640 KB |
Output is correct |
18 |
Correct |
14 ms |
3664 KB |
Output is correct |
19 |
Correct |
11 ms |
3164 KB |
Output is correct |
20 |
Correct |
14 ms |
3408 KB |
Output is correct |
21 |
Correct |
10 ms |
2824 KB |
Output is correct |
22 |
Correct |
12 ms |
3144 KB |
Output is correct |
23 |
Correct |
14 ms |
3432 KB |
Output is correct |
24 |
Correct |
151 ms |
204584 KB |
Output is correct |
25 |
Correct |
165 ms |
204676 KB |
Output is correct |
26 |
Correct |
149 ms |
202120 KB |
Output is correct |
27 |
Correct |
135 ms |
162400 KB |
Output is correct |
28 |
Correct |
93 ms |
42464 KB |
Output is correct |
29 |
Correct |
42 ms |
10336 KB |
Output is correct |