rembocoder

Untitled

Apr 30th, 2023
526
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int int64_t
  6.  
  7. struct node {
  8.     bool is;
  9.     map<char, int> sons;
  10. } trie[1'000'000];
  11. int trie_sz = 1;
  12.  
  13. void add(string& s) {
  14.     int v = 0;
  15.     for (int i = 0; i < s.size(); i++) {
  16.         if (!trie[v].sons.count(s[i])) {
  17.             trie[v].sons[s[i]] = trie_sz++;
  18.         }
  19.         v = trie[v].sons[s[i]];
  20.     }
  21.     trie[v].is = true;
  22. }
  23.  
  24. int find_word(string& s, int st) {
  25.     int v = 0;
  26.     for (int i = st; i < s.size(); i++) {
  27.         if (!trie[v].sons.count(s[i])) {
  28.             break;
  29.         }
  30.         v = trie[v].sons[s[i]];
  31.         if (trie[v].is) {
  32.             return i + 1;
  33.         }
  34.     }
  35.     return s.size() + 1;
  36. }
  37.  
  38. int32_t main() {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(0); cout.tie(0);
  41.     string t;
  42.     getline(cin, t);
  43.     int n;
  44.     cin >> n;
  45.     for (int i = 0; i < n; i++) {
  46.         string s;
  47.         cin >> s;
  48.         add(s);
  49.     }
  50.     int r = t.size() + 1;
  51.     for (int i = 0; i < t.size(); i++) {
  52.         r = min(r, find_word(t, i));
  53.     }
  54.     if (r == t.size() + 1) {
  55.         cout << "YES\n";
  56.         return 0;
  57.     }
  58.     int a, b;
  59.     cin >> a >> b;
  60.     cout << (a * b >= t.size() - r ? "YES\n" : "NO\n");
  61. }
Advertisement
Add Comment
Please, Sign In to add comment