aho-korasik

#include <iostream>
#include <cmath>
#include <vector>
#include <limits.h>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <time.h>
#include <bitset>
#include <queue>
#include <deque>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define all(x) (x).begin(),(x).end()
#define sz(x) (int)x.size()

const int k = 26, MAXN = 100001;

struct node {
    map<char, node*> to, go;
    node* link;
    node* parent;
    char parent_char;
    bool terminal = 0;
    node() {}
    node(char _pch, node* _p) {
        parent_char = _pch;
        parent = _p;
    }
};

node* insert(string& s, node* root) {
    node* v = root;
    for (char c : s) {
        if (!v->to[c]) {
            v->to[c] = new node(c, v);
        }
        v = v->to[c];
    }
    v->terminal = 1;
    return v;
}

node* go(node* v, char c, node* root) {
    if (!v->go[c]) {
        if (v->to[c]) {
            v->go[c] = v->to[c];
        }
        else if (v == root) {
            v->go[c] = root;
        }
        else {
            v->go[c] = go(v->link, c, root);
        }
    }
    return v->go[c];
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    node* root = new node();

    string t;
    cin >> t;

    int n;
    cin >> n;

    vector<string> vec(n);
    map<node*, string> a;
    map<string, bool> b;

    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        node* cur = insert(s, root);
        vec[i] = s;
        a[cur] = s;
        b[s] = 0;
    }

    queue<node*> q;
    root->link = root;
    for (auto p : root->to) {
        p.second->link = root;
        q.push(p.second);
    }

    while (!q.empty()) {
        node* start = q.front();
        q.pop();
        for (auto p : start->to) {
            char pch = p.first;
            node* child = p.second;
            node* psuf = start->link;
            while (psuf != root && !psuf->to[pch]) {
                psuf = psuf->link;
            }
            child->link = (psuf->to[pch] ? psuf->to[pch] : root);
            q.push(child);
        }
    }

    node* v = root;
    for (char c : t) {
        node* u = v;
        u = go(v, c, root);
        while (u != root) {
            if (u->terminal) {
                b[a[u]] = 1;
            }
            u = u->link;
        }
        v = go(v, c, root);
    }

    for (string s : vec) {
        cout << (b[s] ? "Yes\n" : "No\n");
    }

    return 0;
}