ivnikkk

Untitled

May 26th, 2022 (edited)
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #define all(a) a.begin(), a.end()
  5. typedef int ll;
  6. typedef double ld;
  7. struct Node {
  8.     ll go[26];
  9.     ll num;
  10.     bool flag = false;
  11. };
  12. const ll Maxn = 1e5;
  13. Node trie[Maxn];
  14. ll siz = 1;
  15. vector<bool> ans;
  16. void add(string& s, ll i) {
  17.     ll v = 0;
  18.     for (ll i = 0; i < (ll)s.size(); i++) {
  19.         ll c = s[i] - 'a';
  20.         if (trie[v].go[c] == 0) {
  21.             siz++;
  22.             trie[v].go[c] = siz - 1;
  23.         }
  24.         v = trie[v].go[c];
  25.     }
  26.     trie[v].num = i;
  27.     trie[v].flag = true;
  28. }
  29. void find(string& s, ll l, ll r) {
  30.     ll v = 0;
  31.     for (ll i = l; i <= r; i++) {
  32.         ll c = s[i] - 'a';
  33.         if (trie[v].go[c] == 0)
  34.             return;
  35.         v = trie[v].go[c];
  36.     }
  37.     if (trie[v].flag) {
  38.         ans[trie[v].num] = true;
  39.     }
  40.     return;
  41. }
  42. signed main() {
  43. #ifdef _DEBUG
  44.     freopen("input.txt", "r", stdin);
  45.     freopen("output.txt", "w", stdout);
  46. #endif
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(nullptr);
  49.     string sub;
  50.     cin >> sub;
  51.     ll n;
  52.     cin >> n;
  53.     ans.resize(n, false);
  54.     for (ll i = 0; i < n; i++) {
  55.         string s;
  56.         cin >> s;
  57.         add(s, i);
  58.     }
  59.     for (ll d = 1; d <= 30;d++) {
  60.         for (ll i = 0; i <= (ll)sub.size() - d; i++) {
  61.             find(sub, i, i + d - 1);
  62.         }
  63.     }
  64.     for (ll i = 0; i < ans.size(); i++) {
  65.         cout << (ans[i] ? "Yes\n": "No\n");
  66.     }
  67. }
Add Comment
Please, Sign In to add comment