Salvens

D

Aug 10th, 2023
804
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.77 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <array>
  4. #include <vector>
  5. #include <numeric>
  6. #include <random>
  7. #include <chrono>
  8. #include <set>
  9. #include <cassert>
  10.  
  11.  
  12. using namespace std;
  13.  
  14. // #define int long long
  15. #pragma comment(linker,"/STACK:1000000000,1000000000")
  16.  
  17. const long long INF = 1e9 + 7;
  18. const int MAXN = 3e5 + 100;
  19. const int N = 1e5 + 10;
  20.  
  21. struct vertex {
  22.     int next[4];
  23.     int terminal = false;
  24. } v[MAXN];
  25.  
  26. int root = 0, top = 1;
  27.  
  28. inline void add(const string& s) {
  29.     int cur = root;
  30.     for (auto& i: s) {
  31.         int x = i - 'a';
  32.         if (v[cur].next[x] == 0) {
  33.             v[cur].next[x] = top++;
  34.         }
  35.         cur = v[cur].next[x];
  36.     }
  37.     v[cur].terminal = true;
  38. }
  39.  
  40. string test;
  41. int pos;
  42.  
  43. inline bool dfs(int ver, bool was) {
  44.     if (pos == test.size()) {
  45.         return was && v[ver].terminal;
  46.     }
  47.     for (int i = 0; i < 3; ++i) {
  48.         if (v[ver].next[i] != 0) {
  49.             bool res = false;
  50.             if (char(i + 'a') == test[pos]) {
  51.                 ++pos;
  52.                 res = dfs(v[ver].next[i], was);
  53.                 --pos;
  54.             } else {
  55.                 if (!was) {
  56.                     ++pos;
  57.                     res = dfs(v[ver].next[i], true);
  58.                     --pos;
  59.                 }
  60.             }
  61.             if (res) {
  62.                 return true;
  63.             }
  64.         }
  65.     }
  66.     return false;
  67. }
  68.  
  69. signed main() {
  70.     ios_base::sync_with_stdio(false);
  71.     cin.tie(nullptr);
  72.     cout.tie(nullptr);
  73.  
  74.     int n, m;
  75.     cin >> n >> m;
  76.     for (int i = 0; i < n; ++i) {
  77.         string s;
  78.         cin >> s;
  79.         add(s);
  80.     }
  81.     for (int i = 0; i < m; ++i) {
  82.         cin >> test;
  83.         pos = 0;
  84.         cout << (dfs(root, false) ? "YES\n" : "NO\n");
  85.     }
  86. }
Advertisement
Add Comment
Please, Sign In to add comment