#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
using ll = long long;
using pii = pair<int, int>;
const int N = 1e5+5, M = 2e6+5, B = 250, m1 = 1e9+7, m2 = 1e9+9, p = 53;
int mul1(ll x, ll y) {return x*y % m1;}
int mul2(ll x, ll y) {return x*y % m2;}
int pw1[N], pw2[N];
struct hasher {
int n;
vector<int> h1, h2;
void init(string &s) {
n = s.size();
h1.assign(n+2, 0); h2.assign(n+2, 0);
for (int i = n; i >= 1; i--) {
h1[i] = (h1[i+1] + mul1(s[i-1], pw1[100000-i])) % m1;
h2[i] = (h2[i+1] + mul2(s[i-1], pw2[100000-i])) % m2;
}
}
pii get(int l) {
return {mul1(h1[l], pw1[l]), mul2(h2[l], pw2[l])};
}
};
//--------------------------------------
int n, m, ans[N];
string a[N], x[N], y[N];
hasher ha[N], hy[N];
pii vy[N];
struct trie {
struct miniTrie {
int n, ed[M];
int nxt[M][4];
void clear() {
while (n >= 0) {
ed[n] = nxt[n][0] = nxt[n][1] = nxt[n][2] = nxt[n][3] = 0;
n--;
}
n = 0;
}
void add(string &s) {
int id = 0, lim = max(0, (int)s.size()-B+1);
for (int i = s.size() - 1; i >= lim; i--) {
if (!nxt[id][s[i]]) {
nxt[id][s[i]] = ++n;
}
id = nxt[id][s[i]]; ed[id]++;
}
}
int get(string &s) {
int id = 0;
for (int i = s.size() - 1; i >= 0; i--) {
if (!nxt[id][s[i]]) return 0;
id = nxt[id][s[i]];
}
return ed[id];
}
} tree;
int n, nxt[M][4];
vector<int> idx[M], qr[M], qr2[M];
void add(string &s, int idx) {
int id = 0;
for (auto u : s) {
int &val = nxt[id][u];
if (!val) val = ++n;
id = val;
}
qr[id].push_back(idx);
}
vector<pii> vals;
void solve(int id, int len) {
for (auto u : idx[id]) {
tree.add(a[u]);
if (a[u].size() >= B) {
for (auto v : qr2[id]) {
int pos = a[u].size() - y[v].size() + 1;
if (ha[u].get(pos) == vy[v]) {
ans[v]++;
}
}
}
}
for (auto u : qr[id]) {
if (y[u].size() >= B) continue;
ans[u] += tree.get(y[u]);
}
tree.clear();
for (auto u : idx[id]) {
if (a[u].size() < len+1) continue;
int &id2 = nxt[id][a[u][len]];
if (!id2) id2 = ++n;
idx[id2].push_back(u);
}
idx[id].resize(0);
for (int i = 0; i < 4; i++) {
if (nxt[id][i]) solve(nxt[id][i], len+1);
}
}
} tree;
void conv(string &s) {
for (auto &u : s) {
if (u == 'A') u = 0;
if (u == 'G') u = 1;
if (u == 'C') u = 2;
if (u == 'U') u = 3;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
pw1[0] = pw2[0] = 1;
for (int i = 1; i < N; i++) {
pw1[i] = mul1(pw1[i-1], p);
pw2[i] = mul2(pw2[i-1], p);
}
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i]; conv(a[i]);
ha[i].init(a[i]);
tree.idx[0].push_back(i);
}
for (int i = 1; i <= m; i++) {
cin >> x[i] >> y[i];
conv(x[i]); conv(y[i]);
hy[i].init(y[i]); vy[i] = hy[i].get(1);
tree.add(x[i], i);
}
for (int i = 1; i <= tree.n; i++) {
for (auto u : tree.qr[i]) {
if (y[i].size() >= B)
tree.qr2[i].push_back(u);
}
}
tree.solve(0, 0);
for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}
Compilation message
selling_rna.cpp: In member function 'void trie::miniTrie::add(std::string&)':
selling_rna.cpp:52:34: warning: array subscript has type 'char' [-Wchar-subscripts]
52 | if (!nxt[id][s[i]]) {
| ^
selling_rna.cpp:53:33: warning: array subscript has type 'char' [-Wchar-subscripts]
53 | nxt[id][s[i]] = ++n;
| ^
selling_rna.cpp:55:34: warning: array subscript has type 'char' [-Wchar-subscripts]
55 | id = nxt[id][s[i]]; ed[id]++;
| ^
selling_rna.cpp: In member function 'int trie::miniTrie::get(std::string&)':
selling_rna.cpp:62:34: warning: array subscript has type 'char' [-Wchar-subscripts]
62 | if (!nxt[id][s[i]]) return 0;
| ^
selling_rna.cpp:63:34: warning: array subscript has type 'char' [-Wchar-subscripts]
63 | id = nxt[id][s[i]];
| ^
selling_rna.cpp: In member function 'void trie::add(std::string&, int)':
selling_rna.cpp:75:32: warning: array subscript has type 'char' [-Wchar-subscripts]
75 | int &val = nxt[id][u];
| ^
selling_rna.cpp: In member function 'void trie::solve(int, int)':
selling_rna.cpp:103:29: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
103 | if (a[u].size() < len+1) continue;
| ~~~~~~~~~~~~^~~~~~~
selling_rna.cpp:104:41: warning: array subscript has type 'char' [-Wchar-subscripts]
104 | int &id2 = nxt[id][a[u][len]];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
163664 KB |
Output is correct |
| 2 |
Correct |
38 ms |
163676 KB |
Output is correct |
| 3 |
Correct |
36 ms |
163712 KB |
Output is correct |
| 4 |
Correct |
36 ms |
163672 KB |
Output is correct |
| 5 |
Correct |
36 ms |
163672 KB |
Output is correct |
| 6 |
Correct |
36 ms |
163664 KB |
Output is correct |
| 7 |
Correct |
36 ms |
163664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1519 ms |
199020 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
171724 KB |
Output is correct |
| 2 |
Correct |
60 ms |
169212 KB |
Output is correct |
| 3 |
Correct |
61 ms |
170056 KB |
Output is correct |
| 4 |
Correct |
53 ms |
168908 KB |
Output is correct |
| 5 |
Correct |
58 ms |
169612 KB |
Output is correct |
| 6 |
Correct |
58 ms |
170584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
163664 KB |
Output is correct |
| 2 |
Correct |
38 ms |
163676 KB |
Output is correct |
| 3 |
Correct |
36 ms |
163712 KB |
Output is correct |
| 4 |
Correct |
36 ms |
163672 KB |
Output is correct |
| 5 |
Correct |
36 ms |
163672 KB |
Output is correct |
| 6 |
Correct |
36 ms |
163664 KB |
Output is correct |
| 7 |
Correct |
36 ms |
163664 KB |
Output is correct |
| 8 |
Execution timed out |
1519 ms |
199020 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
