#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef pair<int,int> pii;
vector <string> v;
struct node
{
node* a;
node* c;
node* g;
node* u;
int cnt = 0;
int leafshere = 0;
};
node* root1;
node* root2;
void add1(node* root,string s)
{
node* now = root;
now->cnt++;
//acgu lexicograph
for(int i = 0; i < s.length(); i++)
{
if(s[i]=='A')
{
if(now->a == NULL)now->a=new node();
now=now->a;
}
if(s[i]=='C')
{
if(now->c == NULL)now->c=new node();
now=now->c;
}
if(s[i]=='G')
{
if(now->g == NULL)now->g=new node();
now=now->g;
}
if(s[i]=='U')
{
if(now->u == NULL)now->u=new node();
now=now->u;
}
now->cnt++;
}
now->leafshere++;
}
string extract1(node* root)
{
node* now = root;
string ret = "";
now->cnt--;
while(1)
{
if(now->leafshere > 0){now->leafshere-=1;break;}
if(now->a != NULL && now->a->cnt > 0){now=now->a;now->cnt -= 1;ret += 'A';continue;}
if(now->c != NULL && now->c->cnt > 0){now=now->c;now->cnt -= 1;ret += 'C';continue;}
if(now->g != NULL && now->g->cnt > 0){now=now->g;now->cnt -= 1;ret += 'G';continue;}
if(now->u != NULL && now->u->cnt > 0){now=now->u;now->cnt -= 1;ret += 'U';continue;}
break;
}
return ret;
}
node* tree[MAXN*4];
int query1(node* root,string tar)
{
node* now = root;
for(int i = 0; i < tar.length(); i++)
{
if(tar[i]=='A')
{
if(now->a == NULL || now->a->cnt == 0)return 0;
now = now->a;
}
if(tar[i]=='C')
{
if(now->c == NULL || now->c->cnt == 0)return 0;
now = now->c;
}
if(tar[i]=='G')
{
if(now->g == NULL || now->g->cnt == 0)return 0;
now = now->g;
}
if(tar[i]=='U')
{
if(now->u == NULL || now->u->cnt == 0)return 0;
now = now->u;
}
}
return now->cnt;
}
void build(int id,int l,int r)
{
tree[id]=new node();
for(int j = l; j <= r; j++)
{
string z = v[j];
reverse(z.begin(),z.end());
add1(tree[id],z);
}
if(l==r)
{
return ;
}
int mid=l+r>>1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
int query(int id,int left,int right,int l,int r,string target)
{
if(left > right || l > right || left > r)return 0;
if(left >= l && right <= r)
{
//cout << id << " " << left << " " << right << " " << l << " " << r << " " << target << "\n";
return query1(tree[id],target);
}
int mid=left+right>>1;
return query(id*2,left,mid,l,r,target)+query(id*2+1,mid+1,right,l,r,target);
}
pii findbounds(string s)
{
node* now = root2;
int pos = 0;
for(int i = 0; i < s.length(); i++)
{
if(s[i]=='A')
{
if(now->a == NULL || now->a->cnt == 0)return make_pair(-1,-1);
now=now->a;
}
if(s[i]=='C')
{
if(now->c == NULL || now->c->cnt == 0)return make_pair(-1,-1);
if(now->a != NULL)pos += now->a->cnt;
now=now->c;
}
if(s[i]=='G')
{
if(now->g == NULL || now->g->cnt == 0)return make_pair(-1,-1);
if(now->a != NULL)pos += now->a->cnt;
if(now->c != NULL)pos += now->c->cnt;
now=now->g;
}
if(s[i]=='U')
{
if(now->u == NULL || now->u->cnt == 0)return make_pair(-1,-1);
if(now->a != NULL)pos += now->a->cnt;
if(now->c != NULL)pos += now->c->cnt;
if(now->g != NULL)pos += now->g->cnt;
now=now->u;
}
}
return {pos,pos+now->cnt-1};
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin >> n >> m;
root1 = new node();
root2 = new node();
for(int i = 0; i < n; i++)
{
string s;
cin >> s;
add1(root1,s);
add1(root2,s);
}
for(int i = 0; i < n; i++)
{
v.push_back(extract1(root1));
}
build(1,0,n-1);
while(m--)
{
string s,t;
cin >> s >> t;
pii bounds = findbounds(s);
if(bounds == make_pair(-1,-1)){cout << "0\n";continue;}
if(bounds.first < 0 || bounds.second >= n || bounds.first >= n || bounds.second < 0 || bounds.first > bounds.second){cout << "0\n";continue;}
cout << query(1,0,n-1,bounds.first,bounds.second,t) << "\n";
}
//for(int i = 0; i < n; i++)cout << extract1(tree[1]) << "\n";
return 0;
}
/*
2 3
AUGC
AGC
G C
AU C
A C
*/
Compilation message
selling_rna.cpp: In function 'void add1(node*, std::string)':
selling_rna.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int i = 0; i < s.length(); i++)
| ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'int query1(node*, std::string)':
selling_rna.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i = 0; i < tar.length(); i++)
| ~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'void build(int, int, int)':
selling_rna.cpp:111:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
111 | int mid=l+r>>1;
| ~^~
selling_rna.cpp: In function 'int query(int, int, int, int, int, std::string)':
selling_rna.cpp:123:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
123 | int mid=left+right>>1;
| ~~~~^~~~~~
selling_rna.cpp: In function 'pii findbounds(std::string)':
selling_rna.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for(int i = 0; i < s.length(); i++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1354 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
17644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
