Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- typedef int ll;
- typedef double ld;
- struct Node {
- ll go[26];
- ll num;
- bool flag = false;
- };
- const ll Maxn = 1e5;
- Node trie[Maxn];
- ll siz = 1;
- vector<bool> ans;
- void add(string& s, ll i) {
- ll v = 0;
- for (ll i = 0; i < (ll)s.size(); i++) {
- ll c = s[i] - 'a';
- if (trie[v].go[c] == 0) {
- siz++;
- trie[v].go[c] = siz - 1;
- }
- v = trie[v].go[c];
- }
- trie[v].num = i;
- trie[v].flag = true;
- }
- void find(string& s, ll l, ll r) {
- ll v = 0;
- for (ll i = l; i <= r; i++) {
- ll c = s[i] - 'a';
- if (trie[v].go[c] == 0)
- return;
- v = trie[v].go[c];
- }
- if (trie[v].flag) {
- ans[trie[v].num] = true;
- }
- return;
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- string sub;
- cin >> sub;
- ll n;
- cin >> n;
- ans.resize(n, false);
- for (ll i = 0; i < n; i++) {
- string s;
- cin >> s;
- add(s, i);
- }
- for (ll d = 1; d <= 30;d++) {
- for (ll i = 0; i <= (ll)sub.size() - d; i++) {
- find(sub, i, i + d - 1);
- }
- }
- for (ll i = 0; i < ans.size(); i++) {
- cout << (ans[i] ? "Yes\n": "No\n");
- }
- }
Add Comment
Please, Sign In to add comment