#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 P = 1E9 + 7, M = 7;
struct Node {
Node *to[4];
int mn, mx;
Node() {
mn = 1E9, mx = 0;
to[0] = to[1] = to[2] = to[3] = nullptr;
}
};
void add(Node *u, std::string &s, int i, int p) {
if (i == int(s.size())) {
u->mn = std::min(u->mn, p);
u->mx = std::max(u->mx, p);
return;
}
int x = std::string("AGCU").find(s[i]);
if (u->to[x] == nullptr) {
u->to[x] = new Node();
}
add(u->to[x], s, i + 1, p);
u->mn = std::min(u->mn, p);
u->mx = std::max(u->mx, p);
}
std::pair<int, int> find(Node *u, std::string &s, int i) {
if (i == int(s.size())) {
return {u->mn, u->mx};
}
int x = std::string("AGCU").find(s[i]);
if (u->to[x] == nullptr) {
return {-1, -1};
}
return find(u->to[x], s, i + 1);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<std::string> s(n);
Node *root = new Node();
for (int i = 0; i < n; i++) {
std::cin >> s[i];
}
std::sort(s.begin(), s.end());
for (int i = 0; i < n; i++) {
add(root, s[i], 0, i);
}
std::vector<std::tuple<int, int, int, int>> Q;
std::vector<int> f;
for (int i = 0; i < m; i++) {
std::string p, q;
std::cin >> p >> q;
auto [l, r] = find(root, p, 0);
if (l == -1) {
continue;
}
r++;
i64 H = 0;
for (char c : q) {
H *= M;
H += std::string("AGCU").find(c) + 1;
H %= P;
}
Q.emplace_back(l, H, i, -1);
Q.emplace_back(r, H, i, 1);
f.push_back(H);
}
for (int i = 0; i < n; i++) {
i64 h = 0, pw = 1;
for (int j = int(s[i].size()) - 1; j >= 0; j--) {
h = (h + pw * (std::string("AGCU").find(s[i][j]) + 1)) % P;
pw *= M;
pw %= P;
f.push_back(h);
}
}
std::sort(f.begin(), f.end());
f.erase(std::unique(f.begin(), f.end()), f.end());
std::sort(Q.begin(), Q.end());
std::vector<int> ans(m);
// std::vector<int> cnt(f.size());
// std::map<int, int> cnt;
int j = 0;
for (int i = 0; i < n; i++) {
int p, H, id, t;
while (j < int(Q.size())) {
std::tie(p, H, id, t) = Q[j];
if (p != i) {
break;
}
assert(std::binary_search(f.begin(), f.end(), H));
// H = std::lower_bound(f.begin(), f.end(), H) - f.begin();
ans[id] += t * cnt[H];
j++;
}
i64 h = 0, pw = 1;
for (int j = int(s[i].size()) - 1; j >= 0; j--) {
h = (h + pw * (std::string("AGCU").find(s[i][j]) + 1)) % P;
pw *= M;
pw %= P;
assert(std::binary_search(f.begin(), f.end(), h));
// h = std::lower_bound(f.begin(), f.end(), h) - f.begin();
cnt[h]++;
}
}
while (j < int(Q.size())) {
int p, H, id, t;
std::tie(p, H, id, t) = Q[j];
assert(std::binary_search(f.begin(), f.end(), H));
// H = std::lower_bound(f.begin(), f.end(), H) - f.begin();
ans[id] += t * cnt[H];
j++;
}
for (int i = 0; i < m; i++) {
std::cout << ans[i] << "\n";
}
return 0;
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:107:28: error: 'cnt' was not declared in this scope; did you mean 'int'?
107 | ans[id] += t * cnt[H];
| ^~~
| int
selling_rna.cpp:117:13: error: 'cnt' was not declared in this scope; did you mean 'int'?
117 | cnt[h]++;
| ^~~
| int
selling_rna.cpp:125:24: error: 'cnt' was not declared in this scope; did you mean 'int'?
125 | ans[id] += t * cnt[H];
| ^~~
| int
