#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define f first
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
const int mod= 1e9 +7;
const int N=1e5*4;
int ans = 0;
int binpow (int a, int n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return binpow (a, n-1) * a;
else {
int b = binpow (a, n/2);
return b * b;
}
}
vector<int>vis(N);
struct node{
node *next[26];
vector<int>v;
node(){
for(int i = 0; i < 26; i++)next[i] = nullptr;
}
};
node *root = new node();
void add(string s,int ind){
node *cur = root;
for(int i = 0;i<s.size();i++){
if(cur->next[s[i]-'A'] == nullptr)cur->next[s[i]-'A'] = new node();
cur = cur->next[s[i]-'A'];
cur->v.pb(ind);
}
}
void check(string s){
node *cur = root;
for(int i = 0;i<s.size();i++){
if(cur->next[s[i]-'A'] == nullptr)return;
cur = cur->next[s[i]-'A'];
if(s.size()-1==i)for(auto to:cur->v)vis[to]++;
}
}
//------------------2---------------------------------
struct node1{
node1 *next[26];
vector<int>v;
node1(){
for(int i = 0; i < 26; i++)next[i] = nullptr;
}
};
node1 *root1 = new node1();
void add1(string s,int ind){
node1 *cur = root1;
for(int i = 0;i<s.size();i++){
if(cur->next[s[i]-'A'] == nullptr)cur->next[s[i]-'A'] = new node1();
cur = cur->next[s[i]-'A'];
cur->v.pb(ind);
}
}
void check1(string s){
node1 *cur = root1;
for(int i = 0;i<s.size();i++){
if(cur->next[s[i]-'A'] == nullptr)return;
cur = cur->next[s[i]-'A'];
if(s.size()-1==i)for(auto to:cur->v)vis[to]++;
}
}
void solve(){
int n,m,k;
cin >> n >> m;
string s[n];
for(int i = 0; i < n; i++){
cin >> s[i];
add(s[i],i);
}
for(int i = 0; i < n; i++){
reverse(all(s[i]));
add1(s[i],i);
}
//~ check("AA");
while(m--){
string a,b;
cin>> a>> b;
for(int i = 0;i<n;i++)vis[i] = 0;
check(a);
reverse(all(b));
check1(b);
int cnt = 0;
for(int i = 0;i<n;i++)if(vis[i]==2)cnt++;
cout<<cnt<<"\n";
}
}
signed main()
{
// freopen("seq.in", "r", stdin);
// freopen("seq.out", "w", stdout);
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int cnt=0;
int tt=1;//cin>>tt;
while(tt--)solve();
}
Compilation message
sandwich.cpp: In function 'void add(std::string, long long int)':
sandwich.cpp:49:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i = 0;i<s.size();i++){
| ~^~~~~~~~~
sandwich.cpp: In function 'void check(std::string)':
sandwich.cpp:59:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i = 0;i<s.size();i++){
| ~^~~~~~~~~
sandwich.cpp:63:16: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
63 | if(s.size()-1==i)for(auto to:cur->v)vis[to]++;
| ^
sandwich.cpp: In function 'void add1(std::string, long long int)':
sandwich.cpp:83:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(int i = 0;i<s.size();i++){
| ~^~~~~~~~~
sandwich.cpp: In function 'void check1(std::string)':
sandwich.cpp:93:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i = 0;i<s.size();i++){
| ~^~~~~~~~~
sandwich.cpp:97:16: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
97 | if(s.size()-1==i)for(auto to:cur->v)vis[to]++;
| ^
sandwich.cpp: In function 'void solve()':
sandwich.cpp:105:10: warning: unused variable 'k' [-Wunused-variable]
105 | int n,m,k;
| ^
sandwich.cpp: In function 'int main()':
sandwich.cpp:147:6: warning: unused variable 'cnt' [-Wunused-variable]
147 | int cnt=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
