Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int int64_t
- struct node {
- bool is;
- map<char, int> sons;
- } trie[1'000'000];
- int trie_sz = 1;
- void add(string& s) {
- int v = 0;
- for (int i = 0; i < s.size(); i++) {
- if (!trie[v].sons.count(s[i])) {
- trie[v].sons[s[i]] = trie_sz++;
- }
- v = trie[v].sons[s[i]];
- }
- trie[v].is = true;
- }
- int find_word(string& s, int st) {
- int v = 0;
- for (int i = st; i < s.size(); i++) {
- if (!trie[v].sons.count(s[i])) {
- break;
- }
- v = trie[v].sons[s[i]];
- if (trie[v].is) {
- return i + 1;
- }
- }
- return s.size() + 1;
- }
- int32_t main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- string t;
- getline(cin, t);
- int n;
- cin >> n;
- for (int i = 0; i < n; i++) {
- string s;
- cin >> s;
- add(s);
- }
- int r = t.size() + 1;
- for (int i = 0; i < t.size(); i++) {
- r = min(r, find_word(t, i));
- }
- if (r == t.size() + 1) {
- cout << "YES\n";
- return 0;
- }
- int a, b;
- cin >> a >> b;
- cout << (a * b >= t.size() - r ? "YES\n" : "NO\n");
- }
Advertisement
Add Comment
Please, Sign In to add comment