#include<bits/stdc++.h>
using namespace std;
//TRIE
struct node{
node *nxt[26];
int cnt = 0;
node(){
cnt = 0;
for(int i = 0;i<26;i++){
nxt[i] = NULL;
}
}
};
struct node2{
node2 *nxt[26];
int ma = 0 , mi = 0;
node2(){
ma = -1e9;mi = 1e9;
for(int i = 0;i<26;i++){
nxt[i] = NULL;
}
}
};
void inser(string w,node *root,node *nroot){
bool ss = 1;
for(auto ch:w){
if(nroot->nxt[ch-'A']==NULL){
nroot->nxt[ch-'A'] = new node();
}
if(ss){
for(int i = 0;i<26;i++){
if(root->nxt[i]==NULL)continue;
if((ch-'A')!=i)nroot->nxt[i] = root->nxt[i];
nroot->cnt+=root->nxt[i]->cnt;
}
if(root->nxt[ch-'A']==NULL){
ss = 0;
}else root = root->nxt[ch-'A'];
}
nroot-> cnt++;
nroot = nroot->nxt[ch-'A'];
}
nroot->cnt++;
}
void inser2(string w,int idx,node2 *root){
root->ma = max(root->ma,idx);
root->mi = min(root->mi,idx);
for(auto ch:w){
if(root->nxt[ch-'A']==NULL){
root->nxt[ch-'A'] = new node2();
}
root = root->nxt[ch-'A'];
root->ma = max(root->ma,idx);
root->mi = min(root->mi,idx);
}
}
void print(node *root){
for(int i = 0;i<26;i++){
if(root->nxt[i]==NULL)continue;
cout<<char('A'+i)<<","<<root->nxt[i]->cnt<<" ";
print(root->nxt[i]);
}
}
node * version[100001];
int serach1(string w,node * r,node * l){
bool ss = 1;
for(auto ch:w){
if(r->nxt[ch-'A']==NULL)return 0;
r = r->nxt[ch-'A'];
if(!ss)continue;
if(l->nxt[ch-'A']==NULL){
ss = 0;
continue;
}else l = l->nxt[ch-'A'];
}
if(ss)return r->cnt-l->cnt;
else return r->cnt;
}
int search2(string w,string lol,node2 * root){
for(auto ch:w){
if(root->nxt[ch-'A']==NULL){
return 0;
}
root = root->nxt[ch-'A'];
}
int l = root->mi ,r = root->ma;
if(l>r)return 0;
return serach1(lol,version[r],version[l-1]);
}
int main(){
int n,m;
cin>>n>>m;
vector<string> v;
for(int i = 0;i<n;i++){
string s;cin>>s;
v.push_back(s);
}
sort(v.begin(),v.end());
version[0] = new node();
node2 *root = new node2();
for(int i = 0;i<v.size();i++){
version[i+1] = new node();
string xd = v[i];
reverse(xd.begin(),xd.end());
inser(xd,version[i],version[i+1]);
inser2(v[i],i+1,root);
}
while(m--){
string a,b;
cin>>a>>b;
cout<<search2(a,b,root)<<endl;
}
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i = 0;i<v.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
361 ms |
446904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
102 ms |
35620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
