#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();
}
}
Compilation message
/tmp/ccf77Qcd.o: in function `Input()':
selling_rna.cpp:(.text+0xd0): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
selling_rna.cpp:(.text+0x14a): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
/tmp/ccf77Qcd.o: in function `Solve()':
selling_rna.cpp:(.text+0x34a): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
selling_rna.cpp:(.text+0x47f): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
/tmp/ccf77Qcd.o: in function `main':
selling_rna.cpp:(.text.startup+0x12): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
/tmp/ccf77Qcd.o: in function `_GLOBAL__sub_I_trie':
selling_rna.cpp:(.text.startup+0x38): relocation truncated to fit: R_X86_64_PC32 against `.bss'
selling_rna.cpp:(.text.startup+0x52): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(vterminate.o): in function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1e): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x2b): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
