#include<bits/stdc++.h>
#define forinc(i,a,b) for(int i=a;i<=b;i++)
#define fordec(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N = 3e6+10;
int n,m;
string a[N];
struct trie
{
int child[26];
int exist,cnt;
int l,r;
} node[N];
int cur;
void st()
{
memset(node[0].child , -1 ,sizeof node[0].child);
node[0].cnt = node[0].exist = node[0].l = node[0].r = 0 ;
}
int new_(int i)
{
cur++;
memset(node[cur].child , -1 ,sizeof node[cur].child);
node[cur].cnt = node[cur].exist = 0 ;
node[cur].l = node[cur].r = i;
return cur;
}
void ad(string s,int i)
{
int pos = 0;
for(auto f : s)
{
int c = f - 'A';
if(node[pos].child[c] == -1) node[pos].child[c] = new_(i);
pos = node[pos].child[c];
// node[pos].cnt++;
node[pos].r = i;
}
//node[pos].exist++;
}
struct tir
{
int chil[26];
vector<int> v;
}no[N];
int cur2;
void st2()
{
memset(no[0].chil , -1 , sizeof no[0].chil);
no[0].v.clear();
}
int new_2(int i)
{
cur2++;
memset(no[cur2].chil , -1 , sizeof no[cur2].chil);
no[cur2].v.clear();
}
void ad2(string s , int i)
{
int pos = 0;
for(auto f : s)
{
int c = f - 'A';
if(no[pos].chil[c] == -1) no[pos].chil[c] = new_2(i);
pos = no[pos].chil[c];
no[pos].v.pb(i);
}
}
void fin(string s , int &l , int &r)
{
int pos = 0;
for(auto f : s)
{
int c = f - 'A';
if(node[pos].child[c] == -1)
{
l = -1;
r = -1;
return;
}
pos = node[pos].child[c];
}
l = node[pos].l ;
r = node[pos].r ;
}
void fin2(string s , int l , int r)
{
int pos = 0;
for(auto f : s)
{
int c = f - 'A';
if(no[pos].chil[c] == -1)
{
cout<<-1;
return;
}
pos = no[pos].chil[c];
}
int ll = lower_bound(no[pos].v.begin() , no[pos].v.end() , l) - no[pos].v.begin();
int rr = upper_bound(no[pos].v.begin() , no[pos].v.end() , r) - no[pos].v.begin();
cout<<rr - ll<<"\n";
}
int32_t main()
{
#define task "task"
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
forinc(i,1,n) cin>>a[i];
sort(a+1,a+n+1);
st();
forinc(i,1,n) ad(a[i],i);
st2();
forinc(i,1,n)
{
string s = a[i];
reverse(s.begin() , s.end());
ad2(s,i);
}
forinc(i,0,cur2 - 1)
{
sort(no[i].v.begin() , no[i].v.end());
no[i].v.resize(unique(no[i].v.begin() , no[i].v.end()) - no[i].v.begin());
}
forinc(i,1,m)
{
string s1,s2;
cin>>s1>>s2;
int l,r;
fin(s1,l,r);
if(l == -1)
{
cout<<0<<"\n";
continue;
}
fin2(s2,l,r);
}
}
Compilation message
selling_rna.cpp: In function 'int new_2(int)':
selling_rna.cpp:61:1: warning: no return statement in function returning non-void [-Wreturn-type]
61 | }
| ^
selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1284 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1215 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1223 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1284 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
