#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef vector<int> vi;
struct trie{
vi strings;
vector<trie*> cld;
trie(){
cld.assign(4, 0);
}
};
int size = 0;
void insert(trie* t, vi &s, int i){
//cout << i << endl;
if(i == s.size()){ t->strings.pb(size); return;}
auto &c = t->cld[s[i]];
t->strings.pb(size);
if(!c) c = new trie();
insert(c, s, i+1);
}
int cnt(trie *t, vi &s, int i, int l, int r){
if(i == s.size()){
//cout << "Counting ";
//for(int k : t->strings) cout << k << " ";
//cout << endl;
return lower_bound(t->strings.begin(), t->strings.end(), r)
- lower_bound(t->strings.begin(), t->strings.end(), l);
} else {
if(!t->cld[s[i]]) return 0;
return cnt(t->cld[s[i]], s, i+1, l, r);
}
}
struct modTrie{
int sz = 0;
vector<modTrie*> cld;
int l, r;
modTrie(){
cld.assign(16, 0);
}
};
void insert(modTrie* t, vi &s, int i){
if(i == s.size()){ t->sz++; return;}
auto &c = t->cld[s[i]];
if(!c) c = new modTrie();
insert(c, s, i+1);
}
trie *T, *revT;
vi S(0), revS(0);
void dfs(modTrie* t){
t->l = size;
//cout<<t->sz<<endl;
for(int i = 0; i < t->sz; i++) {
insert(T, S, 0);
insert(revT, revS, 0);
size++;
}
for (int i = 0; i < 16; i++) if(t->cld[i]) {
S.pb(i%4); revS.pb(i/4);
dfs(t->cld[i]);
S.pop_back(); revS.pop_back();
}
t->r = size;
}
void getRange(modTrie* t, vi &s, int i, int &l, int &r){
if(i == s.size()){
l = t->l;
r = t->r;
} else {
if(!t->cld[s[i]]){
l = t->l;
r = t->l;
} else getRange(t->cld[s[i]], s, i+1, l, r);
}
}
int val[300];
int N, M;
modTrie* modT;
int main(){
val['A'] = 0;
val['G'] = 1;
val['C'] = 2;
val['U'] = 3;
cin >> N >> M;
modT = new modTrie();
T = new trie();
revT = new trie();
for(int i = 0; i < N; i++){
string s;
cin >> s;
vi S;
for(int j = 0; j < s.size(); j++){
S.pb( val[s[j]] + 4*val[s[s.size() - 1 - j ]] );
}
//cout << "Made S" << endl;
insert(modT, S, 0);
}
dfs(modT);
//cout << "Done " << endl;
for(int i = 0; i < M; i++){
string p, q;
cin >> p >> q;
reverse(q.begin(), q.end());
vi P, Q, S;
for(char c : p) P.pb(val[c]);
for(char c : q) Q.pb(val[c]);
for(int j = 0; j < min(p.size(), q.size()); j++) S.pb(P[j] + 4*Q[j]);
int l, r;
getRange(modT, S, 0, l, r);
//cout << "Range " << l << " " << r << endl;
//cout << "lowest sz " << S.size() << endl;
if(P.size() < Q.size()) {
cout << cnt(revT, Q, 0, l, r) << endl;
} else cout << cnt(T, P, 0, l, r) << endl;
}
}
/*
3 3
AA
AA
AGA
*/
Compilation message
selling_rna.cpp: In function 'void insert(trie*, vi&, int)':
selling_rna.cpp:21:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == s.size()){ t->strings.pb(size); return;}
~~^~~~~~~~~~~
selling_rna.cpp: In function 'int cnt(trie*, vi&, int, int, int)':
selling_rna.cpp:29:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == s.size()){
~~^~~~~~~~~~~
selling_rna.cpp: In function 'void insert(modTrie*, vi&, int)':
selling_rna.cpp:51:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == s.size()){ t->sz++; return;}
~~^~~~~~~~~~~
selling_rna.cpp: In function 'void getRange(modTrie*, vi&, int, int&, int&)':
selling_rna.cpp:77:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == s.size()){
~~^~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:107:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < s.size(); j++){
~~^~~~~~~~~~
selling_rna.cpp:108:27: warning: array subscript has type 'char' [-Wchar-subscripts]
S.pb( val[s[j]] + 4*val[s[s.size() - 1 - j ]] );
^
selling_rna.cpp:108:57: warning: array subscript has type 'char' [-Wchar-subscripts]
S.pb( val[s[j]] + 4*val[s[s.size() - 1 - j ]] );
^
selling_rna.cpp:121:35: warning: array subscript has type 'char' [-Wchar-subscripts]
for(char c : p) P.pb(val[c]);
^
selling_rna.cpp:122:35: warning: array subscript has type 'char' [-Wchar-subscripts]
for(char c : q) Q.pb(val[c]);
^
selling_rna.cpp:123:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < min(p.size(), q.size()); j++) S.pb(P[j] + 4*Q[j]);
~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
4 ms |
504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
576 KB |
Output is correct |
| 5 |
Correct |
3 ms |
576 KB |
Output is correct |
| 6 |
Correct |
3 ms |
576 KB |
Output is correct |
| 7 |
Correct |
4 ms |
576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1579 ms |
611012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
157 ms |
611012 KB |
Output is correct |
| 2 |
Correct |
106 ms |
611012 KB |
Output is correct |
| 3 |
Correct |
184 ms |
611012 KB |
Output is correct |
| 4 |
Correct |
117 ms |
611012 KB |
Output is correct |
| 5 |
Correct |
105 ms |
611012 KB |
Output is correct |
| 6 |
Correct |
132 ms |
611012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
4 ms |
504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
576 KB |
Output is correct |
| 5 |
Correct |
3 ms |
576 KB |
Output is correct |
| 6 |
Correct |
3 ms |
576 KB |
Output is correct |
| 7 |
Correct |
4 ms |
576 KB |
Output is correct |
| 8 |
Execution timed out |
1579 ms |
611012 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
