Class SuffixArray

Strings/Suffix Array Isomorphic.cpp:35–97

  }
}
struct SuffixArray {
  int n;
  vector<int> s;
  vector<int> sa, rank, lcp;
  static const int LG = 18;
  vector<vector<int>> t;
  vector<int> lg;
  SuffixArray() {}
  SuffixArray(vector<int> _s) {
    n = _s.size();
    s = _s;
    for (int i = 0; i < n; i++) str[i] = s[i]; //for integers, each element should be positive
    str[n] = 0;
    suffix_array_DA(n + 1, kinds);
    for (int i = 1; i <= n; i++) sa.push_back(suf[i]);
    rank.resize(n);
    for (int i = 0; i < n; i++) rank[sa[i]] = i;
    costruct_lcp();
    prec();
    build();
  }
  void costruct_lcp() {
    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 prec() {
    lg.resize(n, 0);
    for (int i = 2; i < n; i++) lg[i] = lg[i / 2] + 1;
  }
  void build() {
    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;