Advertisement
Dang_Quan_10_Tin

ANOTHER DICTIONARY PROBLEM

Aug 7th, 2022
858
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.39 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6. using ull = unsigned long long;
  7.  
  8. template <class T>
  9. void read(T &x)
  10. {
  11.     x = 0;
  12.     register int c;
  13.     while ((c = getchar()) && (c > '9' || c < '0'))
  14.         ;
  15.     for (; c >= '0' && c <= '9'; c = getchar())
  16.         x = x * 10 + c - '0';
  17. }
  18.  
  19. constexpr bool typetest = 0;
  20. constexpr int N = 1e5 + 5;
  21.  
  22. // mot node cua cay trie
  23. struct node
  24. {
  25.     node *child[4];
  26.     vector<int> listOfString;
  27.     node()
  28.     {
  29.         for (int i = 0; i < 4; ++i)
  30.             child[i] = NULL;
  31.     }
  32. };
  33.  
  34. #define all(x) (x).begin(), (x).end()
  35.  
  36. int Map(const char &x)
  37. {
  38.     switch (x)
  39.     {
  40.     case 'A':
  41.         return 0;
  42.     case 'U':
  43.         return 1;
  44.     case 'G':
  45.         return 2;
  46.     case 'C':
  47.         return 3;
  48.     default:
  49.         return -1;
  50.     }
  51. }
  52.  
  53. // Cay trie
  54. struct Trie
  55. {
  56.     node root;
  57.  
  58.     void Add(const string &s, const int &v)
  59.     {
  60.         node *a = &root;
  61.         int id = 0;
  62.  
  63.         while (id <= (int)s.size())
  64.         {
  65.             a->listOfString.emplace_back(v);
  66.  
  67.             if (id == (int)s.size())
  68.                 break;
  69.  
  70.             if (!(a->child[Map(s[id])]))
  71.                 a->child[Map(s[id])] = new node;
  72.  
  73.             a = a->child[Map(s[id])];
  74.             ++id;
  75.         }
  76.     }
  77.  
  78.     pair<int, int> Get(const string &s)
  79.     {
  80.         node *a = &root;
  81.         int id = 0;
  82.  
  83.         while (id <= (int)s.size())
  84.         {
  85.             if (id == (int)s.size())
  86.                 return make_pair(a->listOfString[0], a->listOfString.back());
  87.  
  88.             if (!(a->child[Map(s[id])]))
  89.                 return make_pair(-1, -1);
  90.  
  91.             a = a->child[Map(s[id])];
  92.  
  93.             ++id;
  94.         }
  95.  
  96.         return make_pair(-1, -1);
  97.     }
  98.  
  99.     int Cal(const string &s, const int &l, const int &r)
  100.     {
  101.         node *a = &root;
  102.         int id = 0;
  103.  
  104.         while (id <= (int)s.size())
  105.         {
  106.             if (id == (int)s.size())
  107.                 return upper_bound(all(a->listOfString), r) - lower_bound(all(a->listOfString), l);
  108.  
  109.             if (!(a->child[Map(s[id])]))
  110.                 return 0;
  111.  
  112.             a = a->child[Map(s[id])];
  113.  
  114.             ++id;
  115.         }
  116.  
  117.         return 0;
  118.     }
  119. } f, g;
  120.  
  121. int n, m;
  122. string s[N];
  123.  
  124. void Read()
  125. {
  126.     cin >> n >> m;
  127.  
  128.     for (int i = 1; i <= n; ++i)
  129.         cin >> s[i];
  130. }
  131.  
  132. void Solve()
  133. {
  134.     sort(s + 1, s + n + 1);
  135.  
  136.     for (int i = 1; i <= n; ++i)
  137.     {
  138.         string p = s[i];
  139.         reverse(p.begin(), p.end());
  140.  
  141.         f.Add(p, i);
  142.  
  143.         g.Add(s[i], i);
  144.     }
  145.  
  146.     for (int i = 1; i <= m; ++i)
  147.     {
  148.         string p, q;
  149.         cin >> p >> q;
  150.  
  151.         pair<int, int> pos = g.Get(p);
  152.  
  153.         // cout << pos.first << " " << pos.second << "\n";
  154.  
  155.         reverse(q.begin(), q.end());
  156.  
  157.         cout << f.Cal(q, pos.first, pos.second) << "\n";
  158.     }
  159. }
  160.  
  161. int32_t main()
  162. {
  163.     ios::sync_with_stdio(0);
  164.     cin.tie(0);
  165.     cout.tie(0);
  166.     if (fopen("tests.inp", "r"))
  167.     {
  168.         freopen("test.inp", "r", stdin);
  169.         freopen("test.out", "w", stdout);
  170.     }
  171.  
  172.     int t(1);
  173.     if (typetest)
  174.         cin >> t;
  175.     for (int _ = 1; _ <= t; ++_)
  176.     {
  177.         // cout << "Case #" << _ << endl;
  178.         Read();
  179.         Solve();
  180.     }
  181.     // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  182. }
  183.  
  184. /*
  185. 1
  186. 3
  187. 1 0
  188. 1 1 2
  189. 0 3 4
  190. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement