Substring Frequency Suffix array using counting sort

/***
 created: 2022-05-22-10.21.44
***/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

void count_sort(vector<int> &p, const vector<int> &c,int n)
{
    vector<int> p_new(n), cnt(n + 1);
    for(int x : c) cnt[x + 1]++;
    for(int i = 1; i < n; ++i) cnt[i] += cnt[i - 1];
    for(int x : p) p_new[cnt[c[x]]++] = x;
    p = p_new;
}


vector<int> sac(string &s)
{
    s += '$';
    int n = s.length();
    vector<int> p(n), c(n);
    {
        vector<pair<char, int>> a(n);
        for (int i = 0; i < n; i++)
        {
            a[i] = {s[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++)
        {
            if (a[i].first == a[i - 1].first)
                c[p[i]] = c[p[i - 1]];
            else
                c[p[i]] = 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;
        }
        count_sort(p, c, n);

        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> now = {c[p[i]], c[(p[i] + (1 << k)) % n]};
            if (now == prev)
                c_new[p[i]] = c_new[p[i - 1]];
            else
                c_new[p[i]] = c_new[p[i - 1]] + 1;
        }
        k++;
        c = c_new;
    }

    //p.erase(p.begin());

    return p;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);



    string s;
    cin >> s;
    vector<int> sa = sac(s);
    int n = s.size();


    int q;
    cin>>q;
    auto cmp1 = [&](string b,int a){return b < s.substr(a,b.size());};
    auto cmp2 = [&](int a,string b){return s.substr(a,b.size()) < b;};
    while(q--){
        string t;
        cin>>t;
        int z = upper_bound(sa.begin(),sa.end(),t,cmp1) - lower_bound(sa.begin(),sa.end(),t,cmp2);
        cout<<z<<"\n";
    }


    get_lost_idiot;
}