SuffixArray

struct SuffixArray {
  int n;
  std::vector<int> sa;
  std::vector<int> rank;
  std::vector<int> lcp;

  template <typename C>
  SuffixArray(const C& s) {
    assert(!s.empty() && "at Suffix Array constructor");
    n = int(s.size());
    sa.resize(n);
    rank.resize(n);
    lcp.resize(n);
    std::iota(sa.begin(), sa.end(), 0);
    std::sort(sa.begin(), sa.end(), [&](int i, int j) {
      return s[i] < s[j];
    });
    rank[sa[0]] = 0;
    for (int i = 1; i < n; ++i) {
      rank[sa[i]] = rank[sa[i - 1]] + (s[sa[i - 1]] != s[sa[i]]);
    }
    int k = 1;
    while (rank[sa[n - 1]] != n - 1) {
      std::vector<int> sorted_by_second(k);
      std::iota(sorted_by_second.begin(), sorted_by_second.end(), n - k);
      for (const auto& i : sa) {
        if (i >= k) {
          sorted_by_second.push_back(i - k);
        }
      }
      std::vector<int> cnt(n);
      for (int i = 0; i < n; ++i) {
        cnt[rank[i]] += 1;
      }
      std::partial_sum(cnt.begin(), cnt.end(), cnt.begin());
      for (int i = n - 1; i >= 0; --i) {
        sa[--cnt[rank[sorted_by_second[i]]]] = sorted_by_second[i];
      }
      std::vector<int> new_rank(n);
      new_rank[sa[0]] = 0;
      for (int i = 1; i < n; ++i) {
        new_rank[sa[i]] = new_rank[sa[i - 1]] + (rank[sa[i - 1]] != rank[sa[i]] || sa[i - 1] + k == n || rank[sa[i - 1] + k] != rank[sa[i] + k]);
      }
      rank = std::move(new_rank);
      k <<= 1;
    }
    for (int i = 0, j = 0; i < n; ++i) {
      if (rank[i] == 0) {
        continue;
      }
      while (std::max(i, sa[rank[i] - 1]) + j < n && s[i + j] == s[sa[rank[i] - 1] + j]) {
        j += 1;
      }
      lcp[rank[i]] = j;
      j -= !!j;
    }
  }
};