fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define ull unsigned long long
  7. #define initial first
  8. #define added second
  9. #define sort_all(v) sort(v.begin(), v.end())
  10.  
  11. #define ya_sayed_ya_badawy            \
  12.     ios_base::sync_with_stdio(false); \
  13.     cin.tie(NULL);
  14.  
  15. const int MAX = 1e6 + 50;
  16. const int MOD = 1e9 + 7;
  17. const int OO = 1e9;
  18. const double EPS = (double)1e-9;
  19.  
  20. int add(ll a, int b)
  21. {
  22.     return (a + b) % MOD;
  23. }
  24.  
  25. int sub(ll a, int b)
  26. {
  27.     return (a - b + MOD) % MOD;
  28. }
  29.  
  30. int mul(ll a, int b)
  31. {
  32.     return (a * b) % MOD;
  33. }
  34.  
  35. int fp(int a, int pw)
  36. {
  37.     if (!pw)
  38.     {
  39.         return 1;
  40.     }
  41.  
  42.     int ret = fp(a, pw >> 1);
  43.  
  44.     ret = mul(ret, ret);
  45.  
  46.     if (pw & 1)
  47.     {
  48.         ret = mul(ret, a);
  49.     }
  50.     return ret;
  51. }
  52.  
  53. int inv(int a)
  54. {
  55.     return fp(a, MOD - 2);
  56. }
  57.  
  58. int divide(int up, int down)
  59. {
  60.     return mul(up, inv(down));
  61. }
  62.  
  63. const int ALPHA = 26;
  64.  
  65. struct Trie
  66. {
  67.     struct Node
  68.     {
  69.         int child[ALPHA] = {};
  70.         int f = 0;
  71.     };
  72.  
  73.     vector<Node> trie;
  74.  
  75.     Trie()
  76.     {
  77.         trie.emplace_back();
  78.     }
  79.  
  80.     void insert(string &s)
  81.     {
  82.         int node = 0;
  83.         for (auto &i : s)
  84.         {
  85.             int chIdx = i - 'a';
  86.             if (!trie[node].child[chIdx])
  87.             {
  88.                 trie[node].child[chIdx] = trie.size();
  89.                 trie.emplace_back();
  90.             }
  91.             node = trie[node].child[chIdx];
  92.             trie[node].f++;
  93.         }
  94.     }
  95.  
  96.     void erase(string &s)
  97.     {
  98.         int node = 0;
  99.         for (auto &i : s)
  100.         {
  101.             int chIdx = i - 'a';
  102.  
  103.             node = trie[node].child[chIdx];
  104.             trie[node].f--;
  105.         }
  106.     }
  107.  
  108.     int query(string &s)
  109.     {
  110.         int node = 0;
  111.         for (auto &i : s)
  112.         {
  113.             int chIdx = i - 'a';
  114.             if (!trie[trie[node].child[chIdx]].f)
  115.             {
  116.                 return 0;
  117.             }
  118.             node = trie[node].child[chIdx];
  119.         }
  120.         return trie[node].f;
  121.     }
  122. };
  123.  
  124. void solve()
  125. {
  126.     int n, q;
  127.     cin >> n >> q;
  128.  
  129.     Trie tr;
  130.  
  131.     while (n--)
  132.     {
  133.         string s;
  134.         cin >> s;
  135.         tr.insert(s);
  136.     }
  137.  
  138.     while (q--)
  139.     {
  140.         string s;
  141.         cin >> s;
  142.         cout << tr.query(s) << endl;
  143.     }
  144. }
  145.  
  146. signed main()
  147. {
  148.     ya_sayed_ya_badawy int t = 1;
  149.     // cin >> t;
  150.     while (t--)
  151.     {
  152.         solve();
  153.         // cout << endl;
  154.     }
  155.     return 0;
  156. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8q2JmY
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!