#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define shadow ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
const ll INF = 1e18;
const int N = 2e5+7;
/*
A-->0
G-->1
C-->2
U-->3
*/
int n, m;
vector<int> permut[2], ord[2];
int trans(char c){
if(c=='A')
return 0;
if(c=='G')
return 1;
if(c=='C')
return 2;
if(c=='U')
return 3;
}
struct Trie{
struct node{
vector<int> pos;
ll nxt[4]={-1, -1, -1, -1};
int l = -1, r = -1;
// node(int k){
// }
}org;
vector<node> vec;
Trie(){
vec.push_back(org);
}
int len=1;
void add_str(int cur, int k, int id, string &s){
if(vec[cur].nxt[trans(s[k])]==-1){
vec[cur].nxt[trans(s[k])]=len;
len++;
vec.push_back(org);
}
cur=vec[cur].nxt[trans(s[k])];
if(k==s.size()-1){
vec[cur].pos.push_back(id);
return;
}
add_str(cur, k+1, id, s);
}
pii init_order(int k, int idx){
for(auto i:vec[idx].pos){
permut[k].push_back(i);
ord[k][i] = permut[k].size()-1;
}
int lt=-1;
if(vec[idx].pos.size()){
vec[idx].l=vec[idx].pos[0];
vec[idx].r=vec[idx].pos[vec[idx].pos.size()-1];
lt=vec[idx].pos[0];
}
for(int i=0;i<4;i++){
if(vec[idx].nxt[i]!=-1){
pii a = init_order(k, vec[idx].nxt[i]);
vec[idx].r = a.second;
if(lt==-1){
lt=a.first;
}
}
}
vec[idx].l=lt;
return {vec[idx].l, vec[idx].r};
}
pii find_range(int cur, int k, string &s){
//cout<<cur<<' '<<k<<' '<<s<<endl;
if(k==s.size()){
return {vec[cur].l, vec[cur].r};
}
if(vec[cur].nxt[trans(s[k])]==-1){
return {-1, -1};
}
cur = vec[cur].nxt[trans(s[k])];
return find_range(cur, k+1, s);
}
void print(int idx){
cout<<idx<<":\n";
for(auto i:vec[idx].pos){
cout<<i<<' ';
}
cout<<'\n';
for(int i=0;i<4;i++){
cout<<vec[idx].nxt[i]<<' ';
}
cout<<'\n';
cout<<vec[idx].l<<' '<<vec[idx].r<<'\n';
cout<<"\n";
for(int i=0;i<4;i++){
if(vec[idx].nxt[i]!=-1)
print(vec[idx].nxt[i]);
}
}
}trie[2];
int main(){
shadow;
cin>>n>>m;
ord[0].resize(n+1);
ord[1].resize(n+1);
string s;
for(int i=0;i<n;i++){
cin>>s;
trie[0].add_str(0, 0, i+1, s);
reverse(s.begin(), s.end());
trie[1].add_str(0, 0, i+1, s);
}
trie[0].init_order(0, 0);
trie[1].init_order(1, 0);
//trie[0].print(0);
string p, q;
pii rg[2], a = {-1, -1};
for(int i=0;i<m;i++){
int mp[5500];
memset(mp, 0, sizeof mp);
cin>>p>>q;
reverse(q.begin(), q.end());
rg[0] = trie[0].find_range(0, 0, p);
rg[1] = trie[1].find_range(0, 0, q);
if(rg[0]== a||rg[1]==a)
cout<<0<<'\n';
else{
for(int i = 0;i<2;i++){
//cout<<rg[i].first<<' '<<rg[i].second<<'\n';
for(int j=ord[i][rg[i].first];j<=ord[i][rg[i].second];j++){
mp[permut[i][j]]++;
}
}
int ans=0;
for(auto i:mp){
if(i==2)
ans++;
}
cout<<ans<<'\n';
}
}
}
Compilation message
selling_rna.cpp: In member function 'void Trie::add_str(int, int, int, std::string&)':
selling_rna.cpp:57:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | if(k==s.size()-1){
| ~^~~~~~~~~~~~
selling_rna.cpp: In member function 'std::pair<int, int> Trie::find_range(int, int, std::string&)':
selling_rna.cpp:91:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | if(k==s.size()){
| ~^~~~~~~~~~
selling_rna.cpp: In function 'int trans(char)':
selling_rna.cpp:30:1: warning: control reaches end of non-void function [-Wreturn-type]
30 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
134112 KB |
Output is correct |
| 2 |
Correct |
152 ms |
133860 KB |
Output is correct |
| 3 |
Correct |
162 ms |
133428 KB |
Output is correct |
| 4 |
Correct |
152 ms |
134876 KB |
Output is correct |
| 5 |
Correct |
237 ms |
199880 KB |
Output is correct |
| 6 |
Correct |
246 ms |
200288 KB |
Output is correct |
| 7 |
Correct |
59 ms |
4040 KB |
Output is correct |
| 8 |
Correct |
155 ms |
104116 KB |
Output is correct |
| 9 |
Correct |
153 ms |
101428 KB |
Output is correct |
| 10 |
Correct |
140 ms |
101220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
3476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
144 ms |
134112 KB |
Output is correct |
| 9 |
Correct |
152 ms |
133860 KB |
Output is correct |
| 10 |
Correct |
162 ms |
133428 KB |
Output is correct |
| 11 |
Correct |
152 ms |
134876 KB |
Output is correct |
| 12 |
Correct |
237 ms |
199880 KB |
Output is correct |
| 13 |
Correct |
246 ms |
200288 KB |
Output is correct |
| 14 |
Correct |
59 ms |
4040 KB |
Output is correct |
| 15 |
Correct |
155 ms |
104116 KB |
Output is correct |
| 16 |
Correct |
153 ms |
101428 KB |
Output is correct |
| 17 |
Correct |
140 ms |
101220 KB |
Output is correct |
| 18 |
Runtime error |
6 ms |
3476 KB |
Execution killed with signal 11 |
| 19 |
Halted |
0 ms |
0 KB |
- |
