#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FR(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define RF(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
const int MAXN = (int)(1e5) + 5;
const int MAXNODES = (int)(2e6) + 5;
//const int MAXN = 5;
//const int MAXNODES = 20;
struct Node {
int to[4] = {-1, -1, -1, -1};
int leaf = -1;
int cnt = 0;
};
vi prefix[MAXN];
vi suffix[MAXN];
int cur[MAXN];
int ans[MAXN];
vector<Node> nodes;
vi ss[MAXN];
vi ssrev[MAXN];
struct Trie {
int root = -1;
vector<int> leaves;
int sz = 0;
bool st = false;
Trie() {
root = nodes.size();
nodes.push_back({});
}
int add(int i, vi& a) {
sz += a.size();
leaves.push_back(i);
return iter(root, 0, i, a);
}
int iter(int j, int cur, int i, vi& s) {
nodes[j].cnt++;
if (cur == s.size()) {
int old = nodes[j].leaf;
if (old == -1) {
nodes[j].leaf = i;
}
return old;
}
if (nodes[j].to[s[cur]] == -1) {
nodes[j].to[s[cur]] = nodes.size();
nodes.push_back({});
}
return iter(nodes[j].to[s[cur]], cur+1, i, s);
}
int cnt(vi& a, int u, int cur = 0) {
if (u == -1) {
return 0;
}
if (cur == a.size()) {
return nodes[u].cnt;
}
return cnt(a, nodes[u].to[a[cur]], cur+1);
}
};
Trie start;
Trie ts[MAXN];
int tr[MAXNODES];
int merge(int u, int j) {
if (ts[u].sz < ts[j].sz) {
swap(u, j);
}
trav(v, ts[j].leaves) {
ts[u].add(v, ssrev[v]);
}
return u;
}
void dfs(int u, vi& prefixes) {
if (nodes[u].leaf != -1) {
tr[u] = nodes[u].leaf;
}
vi send[5];
trav(a, prefixes) {
if (cur[a] == prefix[a].size()) {
send[4].push_back(a);
}
else {
send[prefix[a][cur[a]++]].push_back(a);
}
}
FR(i, 4) {
if (nodes[u].to[i] != -1) {
dfs(nodes[u].to[i], send[i]);
if (tr[u] == -1) {
tr[u] = tr[nodes[u].to[i]];
}
else {
tr[u] = merge(tr[u], tr[nodes[u].to[i]]);
}
}
}
trav(a, send[4]) {
ans[a] = ts[tr[u]].cnt(suffix[a], ts[tr[u]].root);
}
}
int conv[300];
int main() {
// str s = "input.in";
// freopen(s.c_str(), "r", stdin);
start.st = true;
int N, M;
memset(ans, 0, sizeof(ans));
cin >> N >> M;
conv['A'] = 0;
conv['G'] = 1;
conv['C'] = 2;
conv['U'] = 3;
FR(i, MAXNODES) {
tr[i] = -1;
}
FR(i, N) {
string t;
cin >> t;
FR(j, t.size()) {
ss[i].push_back(conv[t[j]]);
ssrev[i].push_back(conv[t[j]]);
}
reverse(ssrev[i].begin(), ssrev[i].end());
int o = start.add(i, ss[i]);
if (o == -1) {
ts[i].add(i, ssrev[i]);
}
else {
ts[o].add(i, ssrev[i]);
}
}
vi ori;
FR(i, M) {
string pre, suff;
cin >> pre >> suff;
FR(j, pre.size()) {
prefix[i].push_back(conv[pre[j]]);
}
FR(j, suff.size()) {
suffix[i].push_back(conv[suff[j]]);
}
reverse(suffix[i].begin(), suffix[i].end());
ori.push_back(i);
}
dfs(start.root, ori);
FR(i, M) {
cout << ans[i] << '\n';
}
}
Compilation message
selling_rna.cpp: In member function 'int Trie::iter(int, int, int, vi&)':
selling_rna.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | if (cur == s.size()) {
| ~~~~^~~~~~~~~~~
selling_rna.cpp: In member function 'int Trie::cnt(vi&, int, int)':
selling_rna.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | if (cur == a.size()) {
| ~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'void dfs(int, vi&)':
selling_rna.cpp:95:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | if (cur[a] == prefix[a].size()) {
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:17:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
| ^
selling_rna.cpp:18:17: note: in expansion of macro 'FOR'
18 | #define FR(i,a) FOR(i,0,a)
| ^~~
selling_rna.cpp:137:9: note: in expansion of macro 'FR'
137 | FR(j, t.size()) {
| ^~
selling_rna.cpp:138:38: warning: array subscript has type 'char' [-Wchar-subscripts]
138 | ss[i].push_back(conv[t[j]]);
| ^
selling_rna.cpp:139:41: warning: array subscript has type 'char' [-Wchar-subscripts]
139 | ssrev[i].push_back(conv[t[j]]);
| ^
selling_rna.cpp:17:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
| ^
selling_rna.cpp:18:17: note: in expansion of macro 'FOR'
18 | #define FR(i,a) FOR(i,0,a)
| ^~~
selling_rna.cpp:154:9: note: in expansion of macro 'FR'
154 | FR(j, pre.size()) {
| ^~
selling_rna.cpp:155:44: warning: array subscript has type 'char' [-Wchar-subscripts]
155 | prefix[i].push_back(conv[pre[j]]);
| ^
selling_rna.cpp:17:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
| ^
selling_rna.cpp:18:17: note: in expansion of macro 'FOR'
18 | #define FR(i,a) FOR(i,0,a)
| ^~~
selling_rna.cpp:157:9: note: in expansion of macro 'FR'
157 | FR(j, suff.size()) {
| ^~
selling_rna.cpp:158:45: warning: array subscript has type 'char' [-Wchar-subscripts]
158 | suffix[i].push_back(conv[suff[j]]);
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
24288 KB |
Output is correct |
| 2 |
Correct |
17 ms |
24288 KB |
Output is correct |
| 3 |
Correct |
17 ms |
24288 KB |
Output is correct |
| 4 |
Correct |
18 ms |
24288 KB |
Output is correct |
| 5 |
Correct |
18 ms |
24288 KB |
Output is correct |
| 6 |
Correct |
17 ms |
24436 KB |
Output is correct |
| 7 |
Correct |
18 ms |
24288 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1572 ms |
207356 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
82 ms |
32352 KB |
Output is correct |
| 2 |
Correct |
68 ms |
31072 KB |
Output is correct |
| 3 |
Correct |
76 ms |
32224 KB |
Output is correct |
| 4 |
Correct |
68 ms |
30176 KB |
Output is correct |
| 5 |
Correct |
73 ms |
30688 KB |
Output is correct |
| 6 |
Correct |
82 ms |
31968 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
24288 KB |
Output is correct |
| 2 |
Correct |
17 ms |
24288 KB |
Output is correct |
| 3 |
Correct |
17 ms |
24288 KB |
Output is correct |
| 4 |
Correct |
18 ms |
24288 KB |
Output is correct |
| 5 |
Correct |
18 ms |
24288 KB |
Output is correct |
| 6 |
Correct |
17 ms |
24436 KB |
Output is correct |
| 7 |
Correct |
18 ms |
24288 KB |
Output is correct |
| 8 |
Execution timed out |
1572 ms |
207356 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
