Substring_Search

#include <bits/stdc++.h>
using namespace std;

void radix_sort(vector<int>& p, vector<int>& c) {
    int n = p.size();
    vector<int> pos(n), cnt(n, 0), f(n);
    for(int i : c) {
        cnt[i]++;
    }
    pos[0] = 0;
    for(int i = 0; i < n; i++) {
        pos[i] = pos[i-1]+cnt[i-1];
    }
    for(int x : p) {
        f[pos[c[x]]] = x;
        pos[c[x]]++;
    }
    p = f;
}

vector<int> generate(string& t) {
    int n = t.length();
    vector<int> p(n), c(n);
    vector<pair<char, int>> a(n);
    for(int i = 0; i < n; i++) {
        a[i] = {t[i], i};
    }
    sort(a.begin(), a.end());
    for(int i = 0; i < n; i++) {
        p[i] = a[i].second;
    }
    c[p[0]] = 0;
    for(int i = 1; i < n; i++) {
        c[p[i]] = (a[i].first == a[i-1].first) ? c[p[i-1]] : c[p[i-1]]+1;
    }
    int k = 0;
    while((1 << k) < n) {
        for(int i = 0; i < n; i++) {
            p[i] = (p[i]-(1 << k)+n)%n;
        }
        radix_sort(p, c);
        vector<int> c_new(n);
        c_new[p[0]] = 0;
        for(int i = 1; i < n; i++) {
            pair<int, int> prev = {c[p[i-1]], c[(p[i-1]+(1 << k))%n]};
            pair<int, int> curr = {c[p[i]], c[(p[i]+(1 << k))%n]};
            c_new[p[i]] = (prev == curr) ? c_new[p[i-1]] : c_new[p[i-1]]+1;
        }
        c = c_new;
        k++;
    }
    return p;
}

string search(string& st, string& t, vector<int>& p) {
    int s = 0, e = p.size()-1;
    string t1, t2, t3;
    while(e >= s) {
        int m = s+(e-s)/2;
        t1 = (t.length()-p[m] >= st.length()) ? t.substr(p[m], st.length()) : t.substr(p[m]);
        t2 = (t.length()-p[m] >= st.length()) ? t.substr(p[s], st.length()) : t.substr(p[s]);
        t3 = (t.length()-p[m] >= st.length()) ? t.substr(p[e], st.length()) : t.substr(p[e]);
        if(t1 == st) {
            return "Yes\n";
        } else if(t1 < st && st <= t3) {
            s = m+1;
        } else if(t2 <= st && st < t1) {
            e = m-1;
        } else {
            return "No\n";
        }
    }
    return "No\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    string t; int q; cin >> t >> q;
    t += '$';
    vector<int> p = generate(t);
    while(q--) {
        string s; cin >> s;
        cout << search(s, t, p);
    }
}