| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1279919 | hotranminhky0405_ | Selling RNA Strands (JOI16_selling_rna) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int chmap(char c){
if(c=='A') return 0;
if(c=='G') return 1;
if(c=='C') return 2;
return 3;
}
struct Trie
struct Node {
int next[4];
int end_id;
Node(){ fill(begin(next), end(next), -1); end_id = -1; }
};
vector<Node> nodes;
Trie(){ nodes.emplace_back(); }
int add_pattern(const string &s, int pat_id){
int cur = 0;
for(char c: s){
int x = chmap(c);
if(nodes[cur].next[x] == -1){
nodes[cur].next[x] = nodes.size();
nodes.emplace_back();
}
cur = nodes[cur].next[x];
}
if(nodes[cur].end_id == -1) nodes[cur].end_id = pat_id;
return nodes[cur].end_id;
}
template<typename F>
void visit_prefixes_in_string(const string &s, F visitor){
int cur = 0;
for(char c: s){
int x = chmap(c);
if(nodes[cur].next[x] == -1) return;
cur = nodes[cur].next[x];
if(nodes[cur].end_id != -1){
visitor(nodes[cur].end_id);
}
}
}
template<typename F>
void visit_suffixes_in_reversed_string(const string &rev_s, F visitor){
int cur = 0;
for(char c: rev_s){
int x = chmap(c);
if(nodes[cur].next[x] == -1) return;
cur = nodes[cur].next[x];
if(nodes[cur].end_id != -1){
visitor(nodes[cur].end_id);
}
}
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
if(!(cin >> N >> M)) return 0;
vector<string> S(N);
for(int i=0;i<N;i++) cin >> S[i];
vector<pair<string,string>> queries(M);
vector<string> Ps(M), Qs(M);
for(int j=0;j<M;j++){
cin >> Ps[j] >> Qs[j];
queries[j] = {Ps[j], Qs[j]};
}
unordered_map<string,int> pid_map;
unordered_map<string,int> qid_map;
pid_map.reserve(M*2);
qid_map.reserve(M*2);
int pid_cnt = 0, qid_cnt = 0;
vector<int> q_to_pid(M), q_to_qid(M);
for(int j=0;j<M;j++){
auto &p = Ps[j];
auto &q = Qs[j];
auto itp = pid_map.find(p);
if(itp==pid_map.end()){
pid_map[p] = pid_cnt++;
}
auto itq = qid_map.find(q);
if(itq==qid_map.end()){
qid_map[q] = qid_cnt++;
}
}
Trie preTrie, sufTrie;
vector<string> patternsP(pid_cnt);
vector<string> patternsQ(qid_cnt);
for(auto &kv : pid_map) patternsP[kv.second] = kv.first;
for(auto &kv : qid_map) patternsQ[kv.second] = kv.first;
for(int i=0;i<pid_cnt;i++){
preTrie.add_pattern(patternsP[i], i);
}
for(int i=0;i<qid_cnt;i++){
string rq = patternsQ[i];
reverse(rq.begin(), rq.end());
sufTrie.add_pattern(rq, i);
}
vector<vector<int>> listP(pid_cnt), listQ(qid_cnt);
for(int i=0;i<N;i++){
preTrie.visit_prefixes_in_string(S[i], [&](int pid){
listP[pid].push_back(i);
});
string revS = S[i];
reverse(revS.begin(), revS.end());
sufTrie.visit_suffixes_in_reversed_string(revS, [&](int qid){
listQ[qid].push_back(i);
});
}
for(int j=0;j<M;j++){
q_to_pid[j] = pid_map[Ps[j]];
q_to_qid[j] = qid_map[Qs[j]];
}
unordered_map<unsigned long long,int> cache;
cache.reserve(M*2);
for(int j=0;j<M;j++){
int a = q_to_pid[j];
int b = q_to_qid[j];
unsigned long long key = ((unsigned long long)a << 32) | (unsigned long long)(unsigned)b;
auto itc = cache.find(key);
if(itc != cache.end()){
cout << itc->second << '\n';
continue;
}
auto &A = listP[a];
auto &B = listQ[b];
int ans = 0;
if(A.size() <= B.size()){
for(int x: A){
if(binary_search(B.begin(), B.end(), x)) ++ans;
}
}else{
for(int x: B){
if(binary_search(A.begin(), A.end(), x)) ++ans;
}
}
cache[key] = ans;
cout << ans << '\n';
}
return 0;
}