#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 = INT_MAX, r = INT_MIN;
vector<int> v;
string* ogString{};
TrieNode* children[4]{};
TrieNode* parent{};
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);
l = min(child->l, l);
r = max(child->r, r);
}
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;
root->depthFirstSearch(timer);
}
} trie;
struct Eirt
{
TrieNode *root = new TrieNode;
void insert(string& s, const int& index)
{
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)
{
curr->children[d] = new TrieNode;
curr->children[d]->parent = curr;
}
curr = curr->children[d];
}
curr->ogString = &s;
curr->v.push_back(index);
while (curr != root)
{
curr = curr->parent;
curr->v.push_back(index);
}
}
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:50:35: warning: array subscript has type 'char' [-Wchar-subscripts]
50 | int d = chrToHash[s[i]];
| ^
selling_rna.cpp: In member function 'TrieNode* Trie::getNode(const string&)':
selling_rna.cpp:65:35: warning: array subscript has type 'char' [-Wchar-subscripts]
65 | int d = chrToHash[s[i]];
| ^
selling_rna.cpp: In member function 'void Eirt::insert(std::string&, const int&)':
selling_rna.cpp:90:35: warning: array subscript has type 'char' [-Wchar-subscripts]
90 | int d = chrToHash[s[i]];
| ^
selling_rna.cpp: In member function 'TrieNode* Eirt::getNode(const string&)':
selling_rna.cpp:113:35: warning: array subscript has type 'char' [-Wchar-subscripts]
113 | int d = chrToHash[s[i]];
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
184 ms |
249448 KB |
Output is correct |
2 |
Correct |
188 ms |
236124 KB |
Output is correct |
3 |
Correct |
161 ms |
196420 KB |
Output is correct |
4 |
Correct |
170 ms |
187196 KB |
Output is correct |
5 |
Correct |
215 ms |
268568 KB |
Output is correct |
6 |
Correct |
222 ms |
272532 KB |
Output is correct |
7 |
Correct |
48 ms |
10848 KB |
Output is correct |
8 |
Correct |
194 ms |
164868 KB |
Output is correct |
9 |
Correct |
165 ms |
139172 KB |
Output is correct |
10 |
Correct |
125 ms |
135372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
3796 KB |
Output is correct |
2 |
Correct |
11 ms |
2856 KB |
Output is correct |
3 |
Correct |
13 ms |
3276 KB |
Output is correct |
4 |
Correct |
10 ms |
2556 KB |
Output is correct |
5 |
Correct |
12 ms |
2900 KB |
Output is correct |
6 |
Correct |
14 ms |
3148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
184 ms |
249448 KB |
Output is correct |
9 |
Correct |
188 ms |
236124 KB |
Output is correct |
10 |
Correct |
161 ms |
196420 KB |
Output is correct |
11 |
Correct |
170 ms |
187196 KB |
Output is correct |
12 |
Correct |
215 ms |
268568 KB |
Output is correct |
13 |
Correct |
222 ms |
272532 KB |
Output is correct |
14 |
Correct |
48 ms |
10848 KB |
Output is correct |
15 |
Correct |
194 ms |
164868 KB |
Output is correct |
16 |
Correct |
165 ms |
139172 KB |
Output is correct |
17 |
Correct |
125 ms |
135372 KB |
Output is correct |
18 |
Correct |
14 ms |
3796 KB |
Output is correct |
19 |
Correct |
11 ms |
2856 KB |
Output is correct |
20 |
Correct |
13 ms |
3276 KB |
Output is correct |
21 |
Correct |
10 ms |
2556 KB |
Output is correct |
22 |
Correct |
12 ms |
2900 KB |
Output is correct |
23 |
Correct |
14 ms |
3148 KB |
Output is correct |
24 |
Correct |
160 ms |
204448 KB |
Output is correct |
25 |
Correct |
165 ms |
204684 KB |
Output is correct |
26 |
Correct |
157 ms |
201952 KB |
Output is correct |
27 |
Correct |
145 ms |
162404 KB |
Output is correct |
28 |
Correct |
94 ms |
42332 KB |
Output is correct |
29 |
Correct |
45 ms |
10440 KB |
Output is correct |