Shared code

#include "bits/stdc++.h"
using namespace std;
#define dbg(var) cout<<#var<<"="<<var<<" "
#define nl cout<<"\n"
#define fr(i,n) for(int i=0;i<n;i++)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define fa(v) for(auto &i:v)
#define all(v) v.begin(),v.end()
#define sz(v) (int)(v.size())
 
template<typename T> 
vector<int> suffix_array(const T &S) {
    int n = S.size();
    vector<int> sa;
    for (int i = n - 1; i >= 0; --i) {
        sa.push_back(i);
    }
    stable_sort(sa.begin(), sa.end(), [&](int a, int b) { return S[a] < S[b]; });
 
    vector<int> classes(n);
    for (int i = 0; i < n; ++i) {
        classes[i] = S[i];
    }
    for (int len = 1; len < n; len *= 2) {
        vector<int> c = classes;
        for (int i = 0; i < n; i++) {
            classes[sa[i]] =
                i > 0 && c[sa[i - 1]] == c[sa[i]] && sa[i - 1] + len < n && c[sa[i - 1] + len / 2] == c[sa[i] + len / 2]
                    ? classes[sa[i - 1]]
                    : i;
        }
        vector<int> cnt(n);
        iota(cnt.begin(), cnt.end(), 0);
        vector<int> s = sa;
        for (int i = 0; i < n; i++) {
            int s1 = s[i] - len;
            if (s1 >= 0)
                sa[cnt[classes[s1]]++] = s1;
        }
    }
    return sa;
}
template<typename T>
vector<int> lcp_array(const T &s) {
    int n = s.size();
    vector<int> sa = suffix_array(s);
    vector<int> rank(n);
    for (int i = 0; i < n; i++)
        rank[sa[i]] = i;
    vector<int> lcp(n - 1);
    for (int i = 0, h = 0; i < n; i++) {
        if (rank[i] < n - 1) {
            for (int j = sa[rank[i] + 1]; s[i + h] == s[j + h]; ++h)
            ;
            lcp[rank[i]] = h;
            if (h > 0)
                --h;
        }
    }
    return lcp;
}
struct segtree {
   static const int N = 1e5;  // limit for array size
   int n;  // array size
   int t[2 * N];
   
   void build() {  // build the tree
     for (int i = n - 1; i > 0; --i) t[i] = min(t[i<<1] , t[i<<1|1]);
   }
   
   void modify(int p, int value) {  // set value at position p
     for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = min(t[p] , t[p^1]);
   }
   
   int query(int l, int r) {  // sum on interval [l, r)
     int res = 1e9;
     for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
       if (l&1) res = min(res,t[l++]);
       if (r&1) res = min(res,t[--r]);
     }
     return res;
   }
};
int32_t main()
{
   ios_base::sync_with_stdio(0); cin.tie(0);
   string s; cin >> s;
   int n = sz(s);
   auto sfx = suffix_array(s);
   s = s + "$" +  s;
   //for(int x: sfx) cout << x << " " ; cout << "\n";
   segtree ST;
   for(int i = 0 ; i < (int)sfx.size(); i++) {
      ST.t[i + n] = sfx[i];
   }
   ST.n = n;
   ST.build();
   int Q; cin >> Q;
   while(Q--) {
      string pattern; 
      cin >> pattern;
   int l = 0 , r = n - 1,ans = -1, len = pattern.size();
   while(l <= r) {
      int mid = (l + r) / 2;
      if(s.substr(sfx[mid], len) <= pattern) {
         ans = mid;
         l = mid + 1;
      }
      else r = mid - 1;
   }
    int lft = ans;
   l = 0 , r = n - 1,ans = -1, len = pattern.size();
  
   while(l <= r) {
      int mid = (l + r) / 2;
      if(s.substr(sfx[mid], len) >= pattern) {
         ans = mid;
         r = mid - 1;
      }
      else l = mid + 1;
   }
   int rgt = ans;
   if(ans == -1 or s.substr(sfx[ans], len) != pattern) {
      cout << -1 << "\n"; 
      continue;
   }
   //cout << lft << " " << rgt << "\n";
   if(lft > rgt) swap(lft,rgt);
   cout << ST.query(lft,rgt + 1) + 1 << "\n";
   }
   
   
   
   
}