| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1279347 | escobrand | Selling RNA Strands (JOI16_selling_rna) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define all(v) v.begin(),v.end()
#define mk make_pair
#define pb push_back
#define eb emplace_back
typedef pair<int,int> pii;
int id[300];
const int maxn = 1e5 + 10;
int t;
bitset<maxn> bit[maxn*2];
struct Trie
{
struct Node
{
int child[4];
int idx;
vector<int> v;
Node()
{
idx = 0;
for(int i = 0;i<4;i++)child[i] = -1;
}
};
vector<Node> nodes;
int create()
{
nodes.eb();
return nodes.size()-1;
}
Trie()
{
create();
}
void add(string &s ,int idx)
{
int pos = 0;
for(char ch : s)
{
int c = id[ch];
if(nodes[pos].child[c]==-1)nodes[pos].child[c] = create();
pos = nodes[pos].child[c];
nodes[pos].v.eb(idx);
}
}
int cal(string &s)
{
int pos = 0;
for(char ch : s)
{
int c = id[ch];
if(nodes[pos].child[c]==-1)return 0;
pos = nodes[pos].child[c];
}
if(nodes[pos].idx==0)
{
nodes[pos].idx = ++t;
for(const int & k : nodes[pos].v) bit[t].set(k);
}
return nodes[pos].idx;
}
}pre,suf;
int n,m;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
id['A'] = 0;
id['U'] = 1;
id['G'] = 2;
id['C'] = 3;
cin>>n>>m;
for(int i = 0;i<n;i++)
{
string s;
cin>>s;
pre.add(s,i);
reverse(all(s));
suf.add(s,i);
}
while(m--)
{
string p,s;
cin>>p>>s;
int i = pre.cal(p);
int j = suf.cal(s);
if(i&&j)
{
cout<<(bit[i]&bit[j]).count()<<'\n';
}
else cout<<0<<'\n';
}
return 0;
}