| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1069739 | vjudge1 | Selling RNA Strands (JOI16_selling_rna) | C++17 | 0 ms | 0 KiB |
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;
#define fi first
#define se second
#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
int const maxn = 2e6 + 7;
const ll INF = LLONG_MAX;
struct Trie
{
struct Node
{
int child[27][27];
int exist , cnt;
} node[maxn];
int cur;
Trie() : cur(0)
{
memset(node[0].child , -1 , sizeof(node[0].child));
node[0].exist = node[0].cnt = 0;
}
int Make_Note()
{
cur ++;
memset(node[cur].child , -1 , sizeof(node[cur].child));
node[cur].exist = node[cur].cnt = 0;
return cur;
}
void Add_String(string s)
{
int pos = 0;
int le = s.size();
//cout << "le " << le << "\n";
for(int i = 0 ; i < le ; i ++){
int c1 = s[i] - 'A';
int c2 = s[le - 1 - i] - 'A';
//cout << "? " << c1 << " " << c2 << "\n";
if(node[pos].child[c1][c2] == -1){
node[pos].child[c1][c2] = Make_Note();
}
pos = node[pos].child[c1][c2];
node[pos].cnt ++;
}
node[pos].exist ++;
// cout << "cur " << cur << "\n";
}
void Count_On(int& s , int pos , string s1 , int l , int r , int op)
{
//cout << "l r " << l << " " << r << "\n";
if(op == 0){
if(l == r){
int c = s1[l] - 'A';
for(int i = 0 ; i <= 25 ; i ++){
if(node[pos].child[c][i] != -1){
s += node[node[pos].child[c][i]].cnt;
}
}
return;
}
int c = s1[l] - 'A';
for(int i = 0 ; i <= 25 ; i ++){
if(node[pos].child[c][i] != -1){
pos = node[pos].child[c][i];
Count_On(s , pos , s1 , l + 1 , r , op);
}
}
}
else{
if(l == r){
int c = s1[l] - 'A';
for(int i = 0 ; i <= 25 ; i ++){
if(node[pos].child[i][c] != -1){
s += node[node[pos].child[i][c]].cnt;
}
}
return;
}
int c = s1[l] - 'A';
for(int i = 0 ; i <= 25 ; i ++){
if(node[pos].child[i][c] != -1){
pos = node[pos].child[i][c];
Count_On(s , pos , s1 , l + 1 , r , op);
}
}
}
}
int Find_String(string s1 , string s2)
{
int pos = 0;
int le1 = s1.size();
int le2 = s2.size();
int op;
le1 > le2 ? op = 0 : op = 1;
for(int i = 0 ; i < le2 ; i ++){
int c1 = s1[i] - 'A';
int c2 = s2[i] - 'A';
if(node[pos].child[c1][c2] == -1) return 0;
pos = node[pos].child[c1][c2];
}
//cout << "pos " << pos << "\n";
int re = 0;
if(le1 != le2){
if(op == 0) Count_On(re , pos , s1 , le2 , le1 - 1 , op);
else Count_On(re , pos , s2 , le1 , le2 - 1 , op);
}
else{
re += node[pos].cnt;
}
//if(!node[pos].exist) return 0;
return re;
}
};
Trie trie;
int n , q;
string s , s1 , s2;
void Input()
{
cin >> n >> q;
for(int i = 1 ; i <= n ; i ++){
cin >> s;
trie.Add_String(s);
}
}
void Solve()
{
for(int i = 1 ; i <= q ; i ++){
cin >> s1 >> s2;
reverse(s2.begin() , s2.end());
cout << trie.Find_String(s1 , s2) << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(nullptr);
// freopen(".INP","r",stdin);
// freopen(".OUT","w",stdout);
int tt = 1;
//cin >> tt;
while(tt--){
Input();
Solve();
}
}