#include <iostream>
#include <vector>
using namespace std;
#define sz(x) int(x.size())
using vi = vector<int>;
using pii = pair<int, int>;
const int INF = 1'000'000'00;
int fwd_ct = 0;
vi fwd_act_ind(1+100'000);
int bwd_ct = 0;
vi bwd_act_ind(1+100'000);
struct trie
{
vi occ;
vi trav;
trie* child[4] = {NULL, NULL, NULL, NULL};
// int lo = INF;
// int hi = -INF;
pii rng{INF, -INF}; //lo, hi
void insert(int i, vi& s, int l)
{
if(l == sz(s)) occ.push_back(i);
else
{
if(child[s[l]] == NULL) child[s[l]] = new trie;
child[s[l]]->insert(i, s, l+1);
}
}
void traverse(int& ct, vi& act_ind)
{
// cerr << "t enter\n";
for(int i = 0; i < sz(occ); i++)
{
// cerr << "i = " << i << '\n';
trav.push_back(++ct);
// cerr << "pushed\n";
act_ind[occ[i]] = trav[i];
// cerr <<"done\n";
}
for(int y = 0; y < 4; y++)
if(child[y] != NULL)
child[y]->traverse(ct, act_ind);
// cerr << "t exit\n";
}
pii compute_ind()
{
if(!trav.empty())
{
rng.first = trav[0];
rng.second = trav.back();
}
for(int y = 0; y < 4; y++)
{
if(child[y] != NULL)
{
pii z = child[y]->compute_ind();
rng.first = min(rng.first, z.first);
rng.second = max(rng.second, z.second);
}
}
return rng;
}
pii locate(vi& s, int l)
{
if(l == sz(s)) return rng;
else if(child[s[l]] == NULL) return {INF, -INF};
else return child[s[l]]->locate(s, l+1);
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
vi act(1000, -1);
act['A'] = 0;
act['C'] = 1;
act['G'] = 2;
act['U'] = 3;
int N, M;
cin >> N >> M;
trie FWD, BWD;
vi S[1+N], S_rev[1+N];
for(int i = 1; i <= N; i++)
{
string s;
cin >> s;
for(char c: s) S[i].push_back(act[c]);
S_rev[i] = S[i];
reverse(S_rev[i].begin(), S_rev[i].end());
FWD.insert(i, S[i], 0);
BWD.insert(i, S_rev[i], 0);
}
// cerr << "X\n";
FWD.traverse(fwd_ct, fwd_act_ind);
BWD.traverse(bwd_ct, bwd_act_ind);
// cerr << "Y\n";
FWD.compute_ind();
BWD.compute_ind();
//
// cerr << "Z\n";
//
// for(int i = 1; i <= N; i++)
// {
// cerr << i << " : ";
// for(int q = 0; q < sz(S[i]); q++) cerr << S[i][q];
// cerr << " : " << fwd_act_ind[i] << ' ' << bwd_act_ind[i] << '\n';
// }
//
// cerr << "\n\n\n\n\n";
vi f1(1+M), f2(1+M), b1(1+M), b2(1+M);
for(int j = 1; j <= M; j++)
{
string p, q;
cin >> p >> q;
vi P, Q;
for(char p1: p) P.push_back(act[p1]);
for(char q1: q) Q.push_back(act[q1]);
reverse(Q.begin(), Q.end());
pii f = FWD.locate(P, 0);
pii b = BWD.locate(Q, 0);
f1[j] = f.first;
f2[j] = f.second;
b1[j] = b.first;
b2[j] = b.second;
int ans = 0;
for(int i = 1; i <= N; i++)
{
if(f1[j] <= fwd_act_ind[i] && fwd_act_ind[i] <= f2[j])
if(b1[j] <= bwd_act_ind[i] && bwd_act_ind[i] <= b2[j])
ans++;
}
cout << ans << '\n';
}
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:108:9: error: 'reverse' was not declared in this scope
108 | reverse(S_rev[i].begin(), S_rev[i].end());
| ^~~~~~~
selling_rna.cpp:149:9: error: 'reverse' was not declared in this scope
149 | reverse(Q.begin(), Q.end());
| ^~~~~~~
