#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
int child[30][30];
int cnt;
} trie[2000005];
char rna[4]={'A','G','C','U'};
string p,q,s[2000005];
int nnode,n,m,a,b;
int new_node(){
nnode++;
memset(trie[nnode].child, -1, sizeof trie[nnode].child);
trie[nnode].cnt=0;
return nnode;
}
void ins(string s){
int cur=0;
int n=s.size();
for(int i=0; i<n; i++){
int c1=s[i]-'A';
int c2=s[n-i-1]-'A';
if(trie[cur].child[c1][c2]==-1) trie[cur].child[c1][c2]=new_node();
cur=trie[cur].child[c1][c2];
trie[cur].cnt++;
}
}
int dfs1(int u, int k){
int ret=0;
if(k==a-1) return trie[u].cnt;
for(int i=0; i<4; i++){
if(trie[u].child[p[k+1]-'A'][rna[i]-'A']!=-1)
ret+=dfs1(trie[u].child[p[k+1]-'A'][rna[i]-'A'],k+1);
}
return ret;
}
int dfs2(int u, int k){
int ret=0;
if(k==b-1) return trie[u].cnt;
for(int i=0; i<4; i++){
if(trie[u].child[rna[i]-'A'][q[b-k-2]-'A']!=-1)
ret+=dfs2(trie[u].child[rna[i]-'A'][q[b-k-2]-'A'],k+1);
}
return ret;
}
int solve(){
int cur=0;
for(int i=0; i<min(a,b); i++){
int c1=p[i]-'A';
int c2=q[b-i-1]-'A';
if(trie[cur].child[c1][c2]==-1) return 0;
cur=trie[cur].child[c1][c2];
}
if(a>b){
int tmp=dfs1(cur,b-1);
return tmp;
}
if(a<b){
int tmp=dfs2(cur,a-1);
return tmp;
}
return trie[cur].cnt;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
memset(trie[0].child, -1, sizeof(trie[0].child));
trie[0].cnt=0;
for(int i=1; i<=n; i++){
cin>>s[i];
ins(s[i]);
}
while(m--){
cin>>p>>q;
a=p.size(),b=q.size();
cout<<solve()<<'\n';
}
return 0;
}
Compilation message (stderr)
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x60): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x67): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x72): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x87): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x92): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xa7): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xb2): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xc1): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xd4): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cin_sync' defined in .bss._ZN14__gnu_internal12buf_cin_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xdb): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xe2): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
collect2: error: ld returned 1 exit status
