#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;
const int MOD1 = 1e9+7;
int MOD2;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
pii make_hash(string s){
int n = s.size();
int z1 = 5;
int z2 = 5;
pii hb = {0,0};
for(int i=0;i<n;i++){
int c = 1;
if(s[i] == 'C')c=2;
else if(s[i] == 'G')c=3;
else if(s[i] == 'U')c=4;
hb.fi += c * 1LL * z1%MOD1;
hb.se += c * 1LL * z2%MOD2;
if(hb.fi>=MOD1)hb.fi-=MOD1;
if(hb.se>=MOD2)hb.se-=MOD2;
z1 = z1 * 1LL * 5 %MOD1;
z2 = z2 * 1LL * 5 %MOD2;
}
return hb;
}
int cmp(string &a,string &b){
int n = a.size();
int m = b.size();
for(int i=0;i<n;i++){
if(i==m)return 2;
if(b[i] > a[i])return 0; //a is smaller
if(a[i] > b[i])return 2; //a is bigger
}
return 1;
}
const int segsz = 2e7;
int ndcnt = 0;
int cnt[segsz];
int ch[2][segsz];
int upd(int v,int pos,int l,int r){
int nw = ++ndcnt;
if(l==r){
cnt[nw] = cnt[v]+1;
return nw;
}
int tm = (l+r)/2;
cnt[nw] = cnt[v]+1;
if(pos<=tm){
if(!ch[0][v])ch[0][v] = ++ndcnt;
ch[1][nw] = ch[1][v];
ch[0][nw] = upd(ch[0][v],pos,l,tm);
}
else{
if(!ch[1][v])ch[1][v] = ++ndcnt;
ch[0][nw] = ch[0][v];
ch[1][nw] = upd(ch[1][v],pos,tm+1,r);
}
return nw;
}
int query(int v,int l,int r,int pos){
//cout<<l<<" "<<r<<" "<<cnt[v]<<'\n';
if(!v)return 0;
if(l==r)return cnt[v];
int tm = (l+r)/2;
if(pos<=tm)return query(ch[0][v],l,tm,pos);
else return query(ch[1][v],tm+1,r,pos);
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int n,m;
cin>>n>>m;
MOD2 = uniform_int_distribution<int>(1e8,1e9)(rng);
vector<string>s(n);
for(int i=0;i<n;i++)cin>>s[i];
sort(s.begin(),s.end());
vector<vector<pii>>sh(n); //prefix and suffix hash
map<pii,int>labels;
int labelnum = 0;
for(int i=0;i<n;i++){
int k = s[i].size();
sh[i].resize(k);
int z1 = 5;
int z2 = 5;
pii hb = {0,0};
for(int j=0;j<k;j++){
int c = 1;
if(s[i][k-j-1] == 'C')c=2;
else if(s[i][k-j-1] == 'G')c=3;
else if(s[i][k-j-1] == 'U')c=4;
hb.fi += c * 1LL * z1%MOD1;
hb.se += c * 1LL * z2%MOD2;
if(hb.fi>=MOD1)hb.fi-=MOD1;
if(hb.se>=MOD2)hb.se-=MOD2;
z1 = z1 * 1LL * 5 %MOD1;
z2 = z2 * 1LL * 5 %MOD2;
sh[i][j] = hb;
label[hb] = labelnum++;
}
}
vector<int>root(n);
int prev = 0;
for(int i=0;i<n;i++){
//cout<<i<<'\n';
for(pii x:sh[i]){
//prev = upd(prev,labels[x],0,labelnum-1);
//for(int i=0;i<labelnum;i++)cout<<query(prev,0,labelnum-1,i)<<" ";
//cout<<'\n';
}
root[i] = prev;
}
while(m--){
string p,q;
cin>>p>>q;
reverse(q.begin(),q.end());
pii suf = make_hash(q);
int ans = 0;
//binary search for borders l and r
/*
cout<<"comps"<<'\n';
for(int i=0;i<n;i++)cout<<cmp(p,s[i])<<" ";
cout<<'\n';
*/
//this is 2222211111000000 finding a range of 11111111
int l = 0,r = n-1;
while(r>=l){
int mid = (l+r)/2;
if(cmp(p,s[mid]) <=1 )r = mid-1; //p >= s[mid];
else l=mid+1;
}//first guy >= p
int L = l;
l = 0,r = n-1;
while(r>=l){
int mid = (l+r)/2;
if(cmp(p,s[mid]) >=1)l= mid+1; //p <= s[mid]
else r=mid-1;
}
int R = r;
//last guy <= p
//cout<<L<<" "<<R<<'\n';
if(R>=L){
//cout<<labels[suf]<<" "<<L<<" "<<R<<'\n';
int b = q.length();
for(int i=L;i<=R;i++)if(sh[i][b-1] == suf)ans++;
//ans+=query(root[R],0,labelnum-1,labels[suf]);
//if(L)ans-=query(root[L-1],0,labelnum-1,labels[suf]);
}
cout<<ans<<'\n';
}
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:103:4: error: 'label' was not declared in this scope; did you mean 'labels'?
103 | label[hb] = labelnum++;
| ^~~~~
| labels
