#include <bits/stdc++.h>
using namespace std;
int cl () {
cerr << "Time used: " << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
return 0;
}
const int N = (int)1e5;
const char CHAR[4] = {'A', 'C', 'G', 'U'};
int NUM[256];
int n, m;
string s[N + 1];
struct TrieP {
struct Node {
Node *child[4];
int l, r, exist;
Node () : l(N + 1), r(0), exist(0) {
for (int t(0); t < 4; ++t) child[t] = NULL;
}
};
Node *root;
TrieP () {
root = new Node();
}
void Add (const string &x, int id) {
Node *p = root;
for (char f: x) {
int c = NUM[(int)f];
if (p -> child[c] == NULL) p -> child[c] = new Node();
p = p -> child[c];
p -> l = min(p -> l, id);
p -> r = max(p -> r, id);
}
++(p -> exist);
}
pair <int, int> getLR (const string &P) {
Node *p = root;
for (char f: P) {
int c = NUM[(int)f];
if (p -> child[c] == NULL) return make_pair(N + 1, 0);
p = p -> child[c];
}
return make_pair(p -> l, p -> r);
}
string curString = "";
int curI = 0;
void dfs (const Node *p) {
for (int t(0); t < 4; ++t) if (p -> child[t] != NULL) {
curString += CHAR[t];
for (int i(0); i < p -> child[t] -> exist; ++i) {
s[++curI] = curString;
}
dfs(p -> child[t]);
curString.pop_back();
}
}
} tree1;
void init () {
TrieP list;
cin >> n >> m; string x;
for (int i(1); i <= n; ++i) {
cin >> x;
list.Add(x, -1);
}
list.dfs(list.root);
}
struct TrieQ {
struct Node {
Node *child[4];
vector <int> id;
Node () {
for (int t(0); t < 4; ++t) child[t] = NULL;
id.clear();
}
};
Node *root;
TrieQ () {
root = new Node();
}
void Add (string x, int i) {
reverse(x.begin(), x.end());
Node *p = root;
for (char f: x) {
int c = NUM[(int)f];
if (p -> child[c] == NULL) p -> child[c] = new Node();
p = p -> child[c];
(p -> id).push_back(i);
}
}
int getCount (const string &Q, int l, int r) {
if (l > r) return 0;
Node *p = root;
for (char f: Q) {
int c = NUM[(int)f];
if (p -> child[c] == NULL) return 0;
p = p -> child[c];
}
int lo = lower_bound((p -> id).begin(), (p -> id).end(), l) - (p -> id).begin();
int up = upper_bound((p -> id).begin(), (p -> id).end(), r) - (p -> id).begin();
return up - lo;
}
} tree2;
void prep () {
for (int i(1); i <= n; ++i) {
tree1.Add(s[i], i);
tree2.Add(s[i], i);
}
}
int main () {
#define PHILE "base"
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(PHILE".inp", "r")) {
freopen(PHILE".inp", "r", stdin); freopen(PHILE".out", "w", stdout);
}
NUM['A'] = 0;
NUM['C'] = 1;
NUM['G'] = 2;
NUM['U'] = 3;
init();
prep();
string P, Q;
while (m--) {
cin >> P >> Q;
pair <int, int> LR = tree1.getLR(P);
cout << tree2.getCount(Q, LR.first, LR.second) << '\n';
}
return cl();
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:129:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | freopen(PHILE".inp", "r", stdin); freopen(PHILE".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:129:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | freopen(PHILE".inp", "r", stdin); freopen(PHILE".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
3416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
195028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
4824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
3416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
