#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define deb(x) ;
using lli=int;
#ifndef LOCAL
#define endl '\n'
#endif
struct Node{
map<pair<char,char>, lli> next;
lli cant=0;
};
vector<Node> trie;
lli currNode=0;
lli newNode(){
trie.pb(Node());
return currNode++;
}
void addword(string s, bool b,lli ind, lli pt){
for(lli i=ind; i<s.size(); ++i){
if(b){
if(trie[pt].next.find({s[i], 0})==trie[pt].next.end()){
trie[pt].next[{s[i], 0}]=newNode();
}
pt=trie[pt].next[{s[i],0}];
trie[pt].cant++;
}
else{
if(trie[pt].next.find({0,s[i]})==trie[pt].next.end()){
trie[pt].next[{0,s[i]}]=newNode();
}
pt=trie[pt].next[{0,s[i]}];
trie[pt].cant++;
}
}
}
void add(string s){
lli pt=0;
string r=s;
reverse(r.begin(), r.end());
for(lli i=0; i<s.size(); ++i){
deb(i);
trie[pt].cant++;
if(trie[pt].next.find({s[i], r[i]})==trie[pt].next.end()){
trie[pt].next[{s[i], r[i]}]=newNode();
}
addword(s, 1, i, pt);
addword(r, 0, i, pt);
pt=trie[pt].next[{s[i], r[i]}];
}
trie[pt].cant++;
}
lli query(string &p, string &q, lli ind, lli pt){
deb(p);
deb(q);
deb(ind);
deb(pt);
if(p.size()<=ind){
if(q.size()<=ind){
return trie[pt].cant;
}
else{
if(ind==q.size()){
return trie[pt].cant;
}
lli ans=0;
if(trie[pt].next.find({0, q[ind]})!=trie[pt].next.end()){
ans+=query(p,q, ind+1, trie[pt].next[{0, q[ind]}]);
}
return ans;
}
}
else{
if(q.size()<=ind){
if(ind==p.size()){
return trie[pt].cant;
}
lli ans=0;
if(trie[pt].next.find({p[ind],0})!=trie[pt].next.end()){
ans+=query(p,q, ind+1, trie[pt].next[{p[ind],0}]);
}
return ans;
}
else{
if(ind==p.size() && ind==q.size()){
return trie[pt].cant;
}
lli ans=0;
if(trie[pt].next.find({p[ind],q[ind] })!=trie[pt].next.end()){
ans+=query(p,q,ind+1, trie[pt].next[{p[ind], q[ind]}]);
}
return ans;
}
}
}
void solve(){
lli n;
lli m;
cin>>n>>m;
newNode();
deb(n);
for(lli i=0; i<n; ++i){
deb(i);
string s;
cin>>s;
deb(s);
add(s);
}
for(lli i=0; i<m; ++i){
string p,q;
cin>>p>>q;
reverse(q.begin(), q.end());
lli ans=query(p,q,0,0);
cout<<ans<<endl;
}
}
int main(){
ios::ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
freopen("c.in", "r", stdin);
freopen("c.out", "w", stdout);
#endif
lli t=1;
// cin>>t;
while(t--){
solve();
}
}
Compilation message
selling_rna.cpp: In function 'void addword(std::string, bool, lli, lli)':
selling_rna.cpp:24:19: warning: comparison of integer expressions of different signedness: 'lli' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(lli i=ind; i<s.size(); ++i){
| ~^~~~~~~~~
selling_rna.cpp: In function 'void add(std::string)':
selling_rna.cpp:47:17: warning: comparison of integer expressions of different signedness: 'lli' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(lli i=0; i<s.size(); ++i){
| ~^~~~~~~~~
selling_rna.cpp: In function 'lli query(std::string&, std::string&, lli, lli)':
selling_rna.cpp:67:14: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'lli' {aka 'int'} [-Wsign-compare]
67 | if(p.size()<=ind){
| ~~~~~~~~^~~~~
selling_rna.cpp:68:16: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'lli' {aka 'int'} [-Wsign-compare]
68 | if(q.size()<=ind){
| ~~~~~~~~^~~~~
selling_rna.cpp:72:13: warning: comparison of integer expressions of different signedness: 'lli' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if(ind==q.size()){
| ~~~^~~~~~~~~~
selling_rna.cpp:84:16: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'lli' {aka 'int'} [-Wsign-compare]
84 | if(q.size()<=ind){
| ~~~~~~~~^~~~~
selling_rna.cpp:85:16: warning: comparison of integer expressions of different signedness: 'lli' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | if(ind==p.size()){
| ~~~^~~~~~~~~~
selling_rna.cpp:96:13: warning: comparison of integer expressions of different signedness: 'lli' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | if(ind==p.size() && ind==q.size()){
| ~~~^~~~~~~~~~
selling_rna.cpp:96:30: warning: comparison of integer expressions of different signedness: 'lli' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | if(ind==p.size() && ind==q.size()){
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
827 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
600 KB |
Output is correct |
| 2 |
Correct |
36 ms |
6784 KB |
Output is correct |
| 3 |
Correct |
33 ms |
3216 KB |
Output is correct |
| 4 |
Correct |
18 ms |
604 KB |
Output is correct |
| 5 |
Correct |
36 ms |
6696 KB |
Output is correct |
| 6 |
Correct |
32 ms |
3376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| 8 |
Runtime error |
827 ms |
1048576 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
