fully working suffix array template

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

struct SuffixArray
{
  int n, LG;
  string s;
  vector<int> sa, rank, lcp;
  vector<vector<int>> t;
  vector<int> lg;
  SuffixArray() {}
  SuffixArray(string _s)
  {
    n = _s.size();
    LG = log2(n) + 2;
    s = _s;
    sa = build_suffix_array(s);
    rank.resize(n);
    for (int i = 0; i < n; i++)
      rank[sa[i]] = i;
    construct_lcp();
    build();
  }
  vector<int> build_suffix_array(string s)
  { // suffix array of s
    s += '$';
    int n = s.size();
    vector<int> p(n), c(n);
    vector<int> pnew(n), cnew(n), cnt(max(256, n));
    for (char ch : s)
      cnt[ch]++;
    for (int i = 1; i < 256; i++)
      cnt[i] += cnt[i - 1];
    for (int i = 0; i < n; i++)
      p[--cnt[s[i]]] = i;
    for (int i = 1; i < n; i++)
      c[p[i]] = c[p[i - 1]] + (s[p[i]] != s[p[i - 1]]);
    for (int k = 0; (1 << k) < n; k++)
    {
      for (int i = 0; i < n; i++)
        p[i] = (p[i] - (1 << k) + n) % n;
      cnt.assign(n, 0);
      for (auto x : c)
        cnt[x]++;
      for (int i = 1; i < n; i++)
        cnt[i] += cnt[i - 1];
      for (int i = n - 1; i >= 0; i--)
        pnew[--cnt[c[p[i]]]] = p[i];
      p.swap(pnew);
      cnew[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]};
        cnew[p[i]] = cnew[p[i - 1]] + (now != prev);
      }
      c = cnew;
    }
    p.erase(p.begin());
    return p;
  }
  void construct_lcp()
  { // lcp of sa[i] and sa[i + 1]
    int k = 0;
    lcp.resize(n - 1, 0);
    for (int i = 0; i < n; i++)
    {
      if (rank[i] == n - 1)
      {
        k = 0;
        continue;
      }
      int j = sa[rank[i] + 1];
      while (i + k < n && j + k < n && s[i + k] == s[j + k])
        k++;
      lcp[rank[i]] = k;
      if (k)
        k--;
    }
  }
  void build()
  { // sparse table of lcp
    lg.resize(n + 1);
    for (int i = 2; i <= n; i++)
      lg[i] = lg[i >> 1] + 1;

    int sz = n - 1;
    t.resize(sz);

    for (int i = 0; i < sz; i++)
    {
      t[i].resize(LG);
      t[i][0] = lcp[i];
    }

    for (int k = 1; k < LG; ++k)
      for (int i = 0; i + (1 << k) - 1 < sz; ++i)
        t[i][k] = min(t[i][k - 1], t[i + (1 << (k - 1))][k - 1]);
  }
  int query(int l, int r)
  { // minimum of lcp[l], ..., lcp[r]
    int k = lg[r - l + 1];
    return min(t[l][k], t[r - (1 << k) + 1][k]);
  }
  int get_lcp(int i, int j)
  { // lcp of suffix starting from i and j
    if (i == j)
      return n - i;
    int l = rank[i], r = rank[j];
    if (l > r)
      swap(l, r);
    return query(l, r - 1);
  }
  int lower_bound(string &t)
  { // first occurrence of t in sa
    int l = 0, r = n - 1, k = t.size(), ans = n;
    while (l <= r)
    {
      int mid = l + (r - l) / 2;
      if (s.substr(sa[mid], min(n - sa[mid], k)) >= t)
        ans = mid, r = mid - 1;
      else
        l = mid + 1;
    }
    return ans;
  }
  int upper_bound(string &t)
  { // last occurrence of t in sa
    int l = 0, r = n - 1, k = t.size(), ans = n;
    while (l <= r)
    {
      int mid = l + (r - l) / 2;
      if (s.substr(sa[mid], min(n - sa[mid], k)) > t)
        ans = mid, r = mid - 1;
      else
        l = mid + 1;
    }
    return ans;
  }
};

int main()
{
  string s;
  cin >> s;
  SuffixArray sa(s);

  for (int i = 0; i < s.size(); i++)
    cout << sa.sa[i] << " ";
  cout << "\n";

  for (int i = 0; i < s.size() - 1; i++)
    cout << sa.lcp[i] << " ";
}