#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "
const int MAX_N = 1e6 + 10;
struct Node {
int mp[4];
int cnt;
Node() {
for(int i = 0; i < 4; i ++) {
mp[i] = -1;
}
cnt = 0;
}
};
struct Trie {
vector<Node> nds;
Trie() {
nds.resize(1);
}
void add(const string &str) {
int curr = 0;
nds[curr].cnt ++;
for(int i = 0; i < str.size(); i ++) {
if(nds[curr].mp[str[i]] == -1) {
nds[curr].mp[str[i]] = nds.size();
nds.push_back(Node());
}
curr = nds[curr].mp[str[i]];
nds[curr].cnt ++;
}
}
int size() {return nds.size();}
int cnt(const string &str) {
int curr = 0;
for(int i = 0; i < str.size(); i ++) {
curr = nds[i].mp[str[i]];
if(curr == -1) {return 0;}
}
return nds[curr].cnt;
}
void outputtrie(int x, vector<int> out) {
cout << x << " " << nds[x].cnt << " ";
for(auto it : out) {
cout << it;
}
cout << endl;
for(int i = 0; i < 4; i ++) {
if(nds[x].mp[i] == -1) {continue;}
out.push_back(i);
outputtrie(nds[x].mp[i], out);
out.pop_back();
}
}
};
vector<int> fin[MAX_N], quer[MAX_N];
int mp[MAX_N][4];
int n, q, ans[MAX_N], cnt = 1;
string text[MAX_N];
string in[MAX_N][2];
void buildTrie() {
for(int i = 0; i < n; i ++) {
int curr = 0;
for(int j = 0; j < text[i].size(); j ++) {
if(mp[curr][text[i][j]] == -1) {
mp[curr][text[i][j]] = cnt;
cnt ++;
}
curr = mp[curr][text[i][j]];
}
fin[curr].push_back(i);
}
}
void transform(string &str) {
for(auto &it : str) {
if(it == 'A') {
it = 0;
} else if(it == 'U') {
it = 1;
} else if(it == 'G') {
it = 2;
} else if(it == 'C') {
it = 3;
}
}
}
Trie trie[MAX_N];
int who[MAX_N];
void dfsMerge(int x, int y, int ndx, int ndy) {
if(ndy == -1) {return;}
trie[x].nds[ndx].cnt += trie[y].nds[ndy].cnt;
for(int i = 0; i < 4; i ++) {
if(trie[y].nds[ndy].mp[i] == -1) {continue;}
if(trie[x].nds[ndx].mp[i] == -1) {
trie[x].nds[ndx].mp[i] = trie[x].size();
trie[x].nds.push_back(Node());
}
dfsMerge(x, y, trie[x].nds[ndx].mp[i], trie[y].nds[ndy].mp[i]);
}
}
void merge(int x, int y) {
if(trie[who[x]].size() > trie[who[y]].size()) {
swap(who[x], who[y]);
}
dfsMerge(who[x], who[y], 0, 0);
trie[who[y]].nds.resize(0);
}
void dfs(int x) {
for(auto it : fin[x]) {
reverse(text[it].begin(), text[it].end());
trie[who[x]].add(text[it]);
}
for(int i = 0; i < 4; i ++) {
if(mp[x][i] == -1) {continue;}
dfs(mp[x][i]);
merge(x, mp[x][i]);
}
for(auto it : quer[x]) {
ans[it] = trie[who[x]].cnt(in[it][1]);
}
return;
cout << endl;
trie[who[x]].outputtrie(0, {});
cout << endl << endl;
}
void computeAns() {
for(int i = 0; i < q; i ++) {
int curr = 0;
for(int j = 0; j < in[i][0].size(); j ++) {
curr = mp[curr][in[i][0][j]];
if(curr == -1) {
break;
}
}
if(curr == -1) {continue;}
quer[curr].push_back(i);
}
dfs(0);
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
for(int i = 0; i < MAX_N; i ++) {
for(int j = 0; j < 4; j ++) {
mp[i][j] = -1;
}
who[i] = i;
}
cin >> n >> q;
for(int i = 0; i < n; i ++) {
cin >> text[i];
transform(text[i]);
}
buildTrie();
for(int i = 0; i < q; i ++) {
cin >> in[i][0] >> in[i][1];
transform(in[i][0]);
reverse(in[i][1].begin(), in[i][1].end());
transform(in[i][1]);
}
computeAns();
for(int i = 0; i < q; i ++) {
cout << ans[i] << endl;
}
return 0;
}
Compilation message
selling_rna.cpp: In member function 'void Trie::add(const string&)':
selling_rna.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i = 0; i < str.size(); i ++) {
| ~~^~~~~~~~~~~~
selling_rna.cpp:35:26: warning: array subscript has type 'char' [-Wchar-subscripts]
35 | if(nds[curr].mp[str[i]] == -1) {
| ^
selling_rna.cpp:36:24: warning: array subscript has type 'char' [-Wchar-subscripts]
36 | nds[curr].mp[str[i]] = nds.size();
| ^
selling_rna.cpp:39:30: warning: array subscript has type 'char' [-Wchar-subscripts]
39 | curr = nds[curr].mp[str[i]];
| ^
selling_rna.cpp: In member function 'int Trie::cnt(const string&)':
selling_rna.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 0; i < str.size(); i ++) {
| ~~^~~~~~~~~~~~
selling_rna.cpp:47:27: warning: array subscript has type 'char' [-Wchar-subscripts]
47 | curr = nds[i].mp[str[i]];
| ^
selling_rna.cpp: In function 'void buildTrie()':
selling_rna.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int j = 0; j < text[i].size(); j ++) {
| ~~^~~~~~~~~~~~~~~~
selling_rna.cpp:77:26: warning: array subscript has type 'char' [-Wchar-subscripts]
77 | if(mp[curr][text[i][j]] == -1) {
| ^
selling_rna.cpp:78:24: warning: array subscript has type 'char' [-Wchar-subscripts]
78 | mp[curr][text[i][j]] = cnt;
| ^
selling_rna.cpp:81:30: warning: array subscript has type 'char' [-Wchar-subscripts]
81 | curr = mp[curr][text[i][j]];
| ^
selling_rna.cpp: In function 'void computeAns()':
selling_rna.cpp:147:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for(int j = 0; j < in[i][0].size(); j ++) {
| ~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:148:31: warning: array subscript has type 'char' [-Wchar-subscripts]
148 | curr = mp[curr][in[i][0][j]];
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
173 ms |
215660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1609 ms |
834044 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
210 ms |
217096 KB |
Output is correct |
| 2 |
Incorrect |
209 ms |
219500 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
173 ms |
215660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
