Suffix Array (count sub-string) with Binary Search

/*
======================
[     ___T_          ]
[    | 6=6 | =>HI :-)]
[    |__o__|         ]
[ >===]__o[===<      ]
[     [o__]          ]
[      .".           ]
[      |_|           ]
[                    ]
======================
*/

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

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T = 1;
     //~ cin >> T;
     for (int test_case = 1; test_case <= T; ++test_case) {
        string s;
        cin >> s;
        s += '$';
        int n = (int) s.size();
        pair<char,int> a_[n];
        int p[n],c[n];
        for (int i = 0; i < n; ++i) a_[i] = make_pair(s[i],i);
        sort (a_,a_ + n);
        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]] = c[p[i - 1]] + (a_[i].first != a_[i - 1].first);
        for (int k = 0; (1 << k) < n; ++k) {
            pair<pair<int,int>,int> a[n];
            for (int i = 0; i < n; ++i) a[i] = make_pair(make_pair(c[i],c[(i + (1 << k)) % n]),i);
            sort (a,a + n);
            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]] = c[p[i - 1]] + (a[i].first != a[i - 1].first);
        }
        int q;
        cin >> q;
        for (int query = 1; query <= q; ++query) {
            string in;
            cin >> in;
            int l = 0,r = n - 1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                string sub = s.substr(p[mid],(int) in.size());
                r = (sub > in ? mid - 1 : r);
                l = (sub <= in ? mid + 1 : l);
            }
            int left = r,right = r;
            if (s.substr(p[right],(int) in.size()) != in) {
                cout << 0 << "\n";
                continue;
            }
            l = 0,r = n - 1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                string sub = s.substr(p[mid],(int) in.size());
                r = (sub >= in ? mid - 1 : r);
                l = (sub < in ? mid + 1 : l);
            }
            left = l;
            cout << right - left + 1 << "\n";
        }
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}