Suffix Array - count_number_of_substring(CP_Algo_Impleemntation)

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

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

vector<int> sort_cyclic_shifts (string const& s) {
    int n = (int) s.size();
    const int alphabet = 256;
    vector<int> p(n),c(n),cnt(max(alphabet,n),0);
    for (int i = 0; i < n; ++i) ++cnt[s[i]];
    for (int i = 1; i < alphabet; ++i) cnt[i] += cnt[i - 1];
    for (int i = 0; i < n; ++i) p[--cnt[s[i]]] = i;
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; ++i) {
        if (s[p[i]] != s[p[i - 1]]) ++ classes;
        c[p[i]] = classes - 1;
    }
    vector<int> pn(n),cn(n);
    for (int k = 0; (1 << k) < n; ++k) {
        for (int i = 0; i < n; ++i) {
            pn[i] = p[i] - (1 << k);
            if (pn[i] < 0) {
                pn[i] += n;
            }
        }
        fill(cnt.begin(),cnt.begin() + classes,0);
        for (int i = 0; i < n; ++i) ++cnt[c[pn[i]]];
        for (int i = 1; i < classes; ++i) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; --i) p[--cnt[c[pn[i]]]] = pn[i];
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; ++i) {
            pair<int,int> cur = make_pair(c[p[i]],c[(p[i] + (1 << k)) % n]);
            pair<int,int> prev = make_pair(c[p[i - 1]],c[(p[i - 1] + (1 << k)) % n]);
            if (cur != prev) ++classes;
            cn[p[i]] = classes - 1;
        }
        c.swap(cn);
    }
    return p;
}

vector<int> suffix_array_construction (string s) {
    s += '$';
    vector<int> sorted_shifts = sort_cyclic_shifts(s);
    sorted_shifts.erase(sorted_shifts.begin());
    return sorted_shifts;
}

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;
         vector<int> p = suffix_array_construction(s);
         for (int query = 1; query <= 1; ++query) {
             string in;
             cin >> in;
             int l = 0,r = (int) p.size() - 1;
             int left = -1,right = -1;
             while (l <= r) {
                 int mid = l + (r - l) / 2;
                 string sub = s.substr(p[mid],(int) in.size());
                 if (sub > in) {
                     r = mid - 1;
                 } else {
                     l = mid + 1;
                 }
             }
             left = right = r;
             if (right < 0 or right >= (int) p.size()) {
                 cout << 0 << "\n";
                 continue;
             }
             if (s.substr(p[right],(int) in.size()) != in) {
                 cout << 0 << "\n";
                 continue;
             }
             l = 0,r = (int) p.size() - 1;
             while (l <= r) {
                 int mid = l + (r - l) / 2;
                 string sub = s.substr(p[mid],(int) in.size());
                 if (sub >= in) {
                     r = mid - 1;
                 } else {
                     l = mid + 1;
                 }
             }
             left = l;
             cout << right - left + 1 << "\n";

         }
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}