This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef vector<int>::iterator vit;
const int MAXN = (int)1e5 + 10;
const int MAXL = (int)2*1e6 + 10;
vector<int> queries[MAXL],folhas[MAXL];
vector<int> *cjt[MAXL];
string S[MAXN],Q[MAXN];
int Trie1[MAXL][4],Trie2[MAXL][4],ptr1,ptr2;
int resposta[MAXN],sz[MAXL],qtd[MAXL],N,M;
inline int transforma(char c){
if(c == 'A') return 0;
else if(c == 'G') return 1;
else if(c == 'C') return 2;
else return 3;
}
void add_reverse(int idx){
int atual = 1;
for(int i = 0;i<S[idx].size();i++){
int c = transforma(S[idx][i]);
if(Trie2[atual][c]){
atual = Trie2[atual][c];
}
else{
Trie2[atual][c] = ++ptr2;
atual = ptr2;
}
qtd[atual]++;
}
}
void remove_reverse(int idx){
int atual = 1;
for(int i = 0;i<S[idx].size();i++){
int c = transforma(S[idx][i]);
atual = Trie2[atual][c];
qtd[atual]--;
}
}
void add_normal(int idx){
int atual = 1;
for(int i = 0;i<S[idx].size();i++){
int c = transforma(S[idx][i]);
if(Trie1[atual][c]){
atual = Trie1[atual][c];
}
else{
Trie1[atual][c] = ++ptr1;
atual = ptr1;
}
sz[atual] += (int)S[idx].size();
}
folhas[atual].push_back(idx);
}
int query_reverse(int idx){
int atual = 1;
for(int i = 0;i<Q[idx].size();i++){
int c = transforma(Q[idx][i]);
atual = Trie2[atual][c];
}
return qtd[atual];
}
void add_query(int idx){
int atual = 1;
for(int i = 0;i<Q[idx].size();i++){
int c = transforma(Q[idx][i]);
atual = Trie1[atual][c];
}
queries[atual].push_back(idx);
}
void dfs(int v,int keep){
int mx = -1,big = -1;
for(int i = 0;i<4;i++){
int u = Trie1[v][i];
if(!u) continue;
if(sz[u] > mx){
big = u;
mx = sz[u];
}
}
for(int i = 0;i<4;i++){
int u = Trie1[v][i];
if(!u || u == big) continue;
dfs(u,0);
}
if(big != -1){
dfs(big,1);
cjt[v] = cjt[big];
for(vit it = folhas[v].begin();it != folhas[v].end();it++){
add_reverse(*it);
cjt[v]->push_back(*it);
}
}
else{
cjt[v] = new vector<int>();
for(vit it = folhas[v].begin();it != folhas[v].end();it++){
add_reverse(*it);
cjt[v]->push_back(*it);
}
}
for(int i = 0;i<4;i++){
int u = Trie1[v][i];
if(!u || u == big) continue;
for(vit it = cjt[u]->begin();it != cjt[u]->end();it++){
add_reverse(*it);
cjt[v]->push_back(*it);
}
}
for(vit it = queries[v].begin();it != queries[v].end();it++) resposta[*it] = query_reverse(*it);
if(keep == 0){
for(vit it = cjt[v]->begin();it != cjt[v]->end();it++){
remove_reverse(*it);
}
}
}
int main(){
cin.tie(0);ios_base::sync_with_stdio(0);
cin >> N >> M;
ptr1 = ptr2 = 1;
for(int i = 1;i<=N;i++){
cin >> S[i];
add_normal(i);
reverse(S[i].begin(),S[i].end());
}
for(int i = 1;i<=M;i++){
cin >> Q[i];
add_query(i);
cin >> Q[i];
reverse(Q[i].begin(),Q[i].end());
}
dfs(1,1);
for(int i = 1;i<=M;i++) printf("%d\n",resposta[i]);
return 0;
}
Compilation message (stderr)
selling_rna.cpp: In function 'void add_reverse(int)':
selling_rna.cpp:19:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<S[idx].size();i++){
^
selling_rna.cpp: In function 'void remove_reverse(int)':
selling_rna.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<S[idx].size();i++){
^
selling_rna.cpp: In function 'void add_normal(int)':
selling_rna.cpp:41:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<S[idx].size();i++){
^
selling_rna.cpp: In function 'int query_reverse(int)':
selling_rna.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<Q[idx].size();i++){
^
selling_rna.cpp: In function 'void add_query(int)':
selling_rna.cpp:64:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<Q[idx].size();i++){
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |