library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub maspypy/library

:warning: string/sort_substrings.hpp

Depends on

Code

#include "string/suffix_array.hpp"

// dp[i][j]：S[i:i+j) の rank
// 結果のテーブルが使いにくいなら suffix tree を dfs してもらう方がよいかも
template <typename STRING>
vvc<int> sort_substrings(STRING& S, int max_len = -1) {
  int n = len(S);
  if (max_len == -1) max_len = n;
  Suffix_Array sa(S);
  auto& SA = sa.SA;
  auto& LCP = sa.LCP;
  int nxt = 0;
  vv(int, dp, n, max_len + 1, -1);
  FOR(i, len(SA)) {
    auto L = SA[i];
    FOR(k, 1, min(n - L, max_len) + 1) {
      int R = L + k;
      if (i > 0 && LCP[i - 1] >= k)
        dp[L][R - L] = dp[SA[i - 1]][k];
      else
        dp[L][R - L] = nxt++;
    }
  }
  return dp;
}
#line 2 "string/suffix_array.hpp"

#line 2 "alg/monoid/min.hpp"

template <typename E>
struct Monoid_Min {
  using X = E;
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return min(x, y); }
  static constexpr X unit() { return infty<E>; }
  static constexpr bool commute = true;
};
#line 2 "ds/sparse_table/sparse_table.hpp"

// 冪等なモノイドであることを仮定。disjoint sparse table より x 倍高速
template <class Monoid>
struct Sparse_Table {
  using MX = Monoid;
  using X = typename MX::value_type;
  int n, log;
  vvc<X> dat;

  Sparse_Table() {}
  Sparse_Table(int n) { build(n); }
  template <typename F>
  Sparse_Table(int n, F f) {
    build(n, f);
  }
  Sparse_Table(const vc<X>& v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> X { return MX::unit(); });
  }
  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m, log = 1;
    while ((1 << log) < n) ++log;
    dat.resize(log);
    dat[0].resize(n);
    FOR(i, n) dat[0][i] = f(i);

    FOR(i, log - 1) {
      dat[i + 1].resize(len(dat[i]) - (1 << i));
      FOR(j, len(dat[i]) - (1 << i)) {
        dat[i + 1][j] = MX::op(dat[i][j], dat[i][j + (1 << i)]);
      }
    }
  }

  X prod(int L, int R) {
    if (L == R) return MX::unit();
    if (R == L + 1) return dat[0][L];
    int k = topbit(R - L - 1);
    return MX::op(dat[k][L], dat[k][R - (1 << k)]);
  }

  template <class F>
  int max_right(const F check, int L) {
    assert(0 <= L && L <= n && check(MX::unit()));
    if (L == n) return n;
    int ok = L, ng = n + 1;
    while (ok + 1 < ng) {
      int k = (ok + ng) / 2;
      bool bl = check(prod(L, k));
      if (bl) ok = k;
      if (!bl) ng = k;
    }
    return ok;
  }

  template <class F>
  int min_left(const F check, int R) {
    assert(0 <= R && R <= n && check(MX::unit()));
    if (R == 0) return 0;
    int ok = R, ng = -1;
    while (ng + 1 < ok) {
      int k = (ok + ng) / 2;
      bool bl = check(prod(k, R));
      if (bl) ok = k;
      if (!bl) ng = k;
    }
    return ok;
  }
};
#line 2 "ds/segtree/segtree.hpp"

template <class Monoid>
struct SegTree {
  using MX = Monoid;
  using X = typename MX::value_type;
  using value_type = X;
  vc<X> dat;
  int n, log, size;

  SegTree() {}
  SegTree(int n) { build(n); }
  template <typename F>
  SegTree(int n, F f) {
    build(n, f);
  }
  SegTree(const vc<X>& v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> X { return MX::unit(); });
  }
  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m, log = 1;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    dat.assign(size << 1, MX::unit());
    FOR(i, n) dat[size + i] = f(i);
    FOR_R(i, 1, size) update(i);
  }

  X get(int i) { return dat[size + i]; }
  vc<X> get_all() { return {dat.begin() + size, dat.begin() + size + n}; }

  void update(int i) { dat[i] = Monoid::op(dat[2 * i], dat[2 * i + 1]); }
  void set(int i, const X& x) {
    assert(i < n);
    dat[i += size] = x;
    while (i >>= 1) update(i);
  }

  void multiply(int i, const X& x) {
    assert(i < n);
    i += size;
    dat[i] = Monoid::op(dat[i], x);
    while (i >>= 1) update(i);
  }

  X prod(int L, int R) {
    assert(0 <= L && L <= R && R <= n);
    X vl = Monoid::unit(), vr = Monoid::unit();
    L += size, R += size;
    while (L < R) {
      if (L & 1) vl = Monoid::op(vl, dat[L++]);
      if (R & 1) vr = Monoid::op(dat[--R], vr);
      L >>= 1, R >>= 1;
    }
    return Monoid::op(vl, vr);
  }

  vc<int> prod_ids(int L, int R) {
    assert(0 <= L && L <= R && R <= n);
    vc<int> I, J;
    L += size, R += size;
    while (L < R) {
      if (L & 1) I.eb(L++);
      if (R & 1) J.eb(--R);
      L >>= 1, R >>= 1;
    }
    reverse(all(J));
    concat(I, J);
    return I;
  }

  X prod_all() { return dat[1]; }

  template <class F>
  int max_right(F check, int L) {
    assert(0 <= L && L <= n && check(Monoid::unit()));
    if (L == n) return n;
    L += size;
    X sm = Monoid::unit();
    do {
      while (L % 2 == 0) L >>= 1;
      if (!check(Monoid::op(sm, dat[L]))) {
        while (L < size) {
          L = 2 * L;
          if (check(Monoid::op(sm, dat[L]))) {
            sm = Monoid::op(sm, dat[L++]);
          }
        }
        return L - size;
      }
      sm = Monoid::op(sm, dat[L++]);
    } while ((L & -L) != L);
    return n;
  }

  template <class F>
  int min_left(F check, int R) {
    assert(0 <= R && R <= n && check(Monoid::unit()));
    if (R == 0) return 0;
    R += size;
    X sm = Monoid::unit();
    do {
      --R;
      while (R > 1 && (R % 2)) R >>= 1;
      if (!check(Monoid::op(dat[R], sm))) {
        while (R < size) {
          R = 2 * R + 1;
          if (check(Monoid::op(dat[R], sm))) {
            sm = Monoid::op(dat[R--], sm);
          }
        }
        return R + 1 - size;
      }
      sm = Monoid::op(dat[R], sm);
    } while ((R & -R) != R);
    return 0;
  }

  // prod_{l<=i<r} A[i xor x]
  X xor_prod(int l, int r, int xor_val) {
    static_assert(Monoid::commute);
    X x = Monoid::unit();
    for (int k = 0; k < log + 1; ++k) {
      if (l >= r) break;
      if (l & 1) {
        x = Monoid::op(x, dat[(size >> k) + ((l++) ^ xor_val)]);
      }
      if (r & 1) {
        x = Monoid::op(x, dat[(size >> k) + ((--r) ^ xor_val)]);
      }
      l /= 2, r /= 2, xor_val /= 2;
    }
    return x;
  }
};
#line 2 "ds/sparse_table/disjoint_sparse_table.hpp"

template <class Monoid>
struct Disjoint_Sparse_Table {
  using MX = Monoid;
  using X = typename MX::value_type;
  int n, log;
  vvc<X> dat;

  Disjoint_Sparse_Table() {}
  Disjoint_Sparse_Table(int n) { build(n); }
  template <typename F>
  Disjoint_Sparse_Table(int n, F f) {
    build(n, f);
  }
  Disjoint_Sparse_Table(const vc<X>& v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> X { return MX::unit(); });
  }
  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m, log = 1;
    while ((1 << log) < n) ++log;
    dat.resize(log);
    dat[0].reserve(n);
    FOR(i, n) dat[0].eb(f(i));
    FOR(i, 1, log) {
      auto& v = dat[i];
      v = dat[0];
      int b = 1 << i;
      for (int m = b; m <= n; m += 2 * b) {
        int L = m - b, R = min(n, m + b);
        FOR_R(j, L + 1, m) v[j - 1] = MX::op(v[j - 1], v[j]);
        FOR(j, m, R - 1) v[j + 1] = MX::op(v[j], v[j + 1]);
      }
    }
  }

  X prod(int L, int R) {
    if (L == R) return MX::unit();
    --R;
    if (L == R) return dat[0][L];
    int k = topbit(L ^ R);
    return MX::op(dat[k][L], dat[k][R]);
  }

  template <class F>
  int max_right(const F check, int L) {
    assert(0 <= L && L <= n && check(MX::unit()));
    if (L == n) return n;
    int ok = L, ng = n + 1;
    while (ok + 1 < ng) {
      int k = (ok + ng) / 2;
      bool bl = check(prod(L, k));
      if (bl) ok = k;
      if (!bl) ng = k;
    }
    return ok;
  }

  template <class F>
  int min_left(const F check, int R) {
    assert(0 <= R && R <= n && check(MX::unit()));
    if (R == 0) return 0;
    int ok = R, ng = -1;
    while (ng + 1 < ok) {
      int k = (ok + ng) / 2;
      bool bl = check(prod(k, R));
      if (bl) ok = k;
      if (!bl) ng = k;
    }
    return ok;
  }
};
#line 3 "ds/static_range_product.hpp"

/*
参考：https://judge.yosupo.jp/submission/106668
長さ 2^LOG のブロックに分ける．ブロック内の prefix, suffix を持つ．
ブロック積の列を ST(DST) で持つ．ブロックをまたぐ積は O(1).
短いものは O(1) を諦めて愚直ということにする．
前計算：O(Nlog(N)/2^LOG)
クエリ：O(1) / worst O(2^LOG)
*/
template <typename Monoid, typename SPARSE_TABLE, int LOG = 4>
struct Static_Range_Product {
  using MX = Monoid;
  using X = typename MX::value_type;
  int N, b_num;
  vc<X> A, pre, suf; // inclusive
  SPARSE_TABLE ST;

  Static_Range_Product() {}
  template <typename F>
  Static_Range_Product(int n, F f) {
    build(n, f);
  }
  Static_Range_Product(const vc<X>& v) { build(v); }

  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    N = m;
    b_num = N >> LOG;
    A.resize(N);
    FOR(i, N) A[i] = f(i);
    pre = A, suf = A;
    constexpr int mask = (1 << LOG) - 1;
    FOR(i, 1, N) {
      if (i & mask) pre[i] = MX::op(pre[i - 1], A[i]);
    }
    FOR_R(i, 1, N) {
      if (i & mask) suf[i - 1] = MX::op(A[i - 1], suf[i]);
    }
    ST.build(b_num, [&](int i) -> X { return suf[i << LOG]; });
  }

  // O(1) or O(R-L)
  X prod(int L, int R) {
    if (L == R) return MX::unit();
    R -= 1;
    int a = L >> LOG, b = R >> LOG;
    if (a < b) {
      X x = ST.prod(a + 1, b);
      x = MX::op(suf[L], x);
      x = MX::op(x, pre[R]);
      return x;
    }
    X x = A[L];
    FOR(i, L + 1, R + 1) x = MX::op(x, A[i]);
    return x;
  }

  template <class F>
  int max_right(const F check, int L) {
    assert(0 <= L && L <= N && check(MX::unit()));
    if (L == N) return N;
    int ok = L, ng = N + 1;
    while (ok + 1 < ng) {
      int k = (ok + ng) / 2;
      bool bl = check(prod(L, k));
      if (bl) ok = k;
      if (!bl) ng = k;
    }
    return ok;
  }

  template <class F>
  int min_left(const F check, int R) {
    assert(0 <= R && R <= N && check(MX::unit()));
    if (R == 0) return 0;
    int ok = R, ng = -1;
    while (ng + 1 < ok) {
      int k = (ok + ng) / 2;
      bool bl = check(prod(k, R));
      if (bl) ok = k;
      if (!bl) ng = k;
    }
    return ok;
  }
};
#line 7 "string/suffix_array.hpp"

// 辞書順 i 番目の suffix が j 文字目始まりであるとき、
// SA[i] = j, ISA[j] = i
// |S|>0 を前提（そうでない場合 dummy 文字を追加して利用せよ）
// SEG_TYPE=0: SegTree, 1: SparseTable, 2: StaticRangeProduct
template <int SEG_TYPE = 0>
struct Suffix_Array {
  vc<int> SA;
  vc<int> ISA;
  vc<int> LCP;
  using Mono = Monoid_Min<int>;
  using SEG0 = SegTree<Mono>;
  using SEG1 = Sparse_Table<Mono>;
  using SEG2 = Static_Range_Product<Mono, Sparse_Table<Mono>, 4>;
  static_assert(SEG_TYPE == 0 || SEG_TYPE == 1 || SEG_TYPE == 2);
  using SegType = conditional_t<SEG_TYPE == 0, SEG0,
                                conditional_t<SEG_TYPE == 1, SEG1, SEG2> >;
  SegType seg;
  bool build_seg;

  Suffix_Array() {}
  Suffix_Array(string& s) {
    build_seg = 0;
    assert(len(s) > 0);
    char first = 127, last = 0;
    for (auto&& c : s) {
      chmin(first, c);
      chmax(last, c);
    }
    SA = calc_suffix_array(s, first, last);
    calc_LCP(s);
  }

  Suffix_Array(vc<int> s) {
    build_seg = 0;
    assert(len(s) > 0);
    SA = calc_suffix_array(s);
    calc_LCP(s);
  }

  // lcp(S[i:], S[j:])
  int lcp(int i, int j) {
    if (!build_seg) {
      build_seg = true;
      seg.build(LCP);
    }
    int n = len(SA);
    if (i == n || j == n) return 0;
    if (i == j) return n - i;
    i = ISA[i], j = ISA[j];
    if (i > j) swap(i, j);
    return seg.prod(i, j);
  }

  // S[i:] との lcp が n 以上であるような半開区間
  pair<int, int> lcp_range(int i, int n) {
    if (!build_seg) {
      build_seg = true;
      seg.build(LCP);
    }
    i = ISA[i];
    int a = seg.min_left([&](auto e) -> bool { return e >= n; }, i);
    int b = seg.max_right([&](auto e) -> bool { return e >= n; }, i);
    return {a, b + 1};
  }

  // -1: S[L1:R1) < S[L2, R2)
  //  0: S[L1:R1) = S[L2, R2)
  // +1: S[L1:R1) > S[L2, R2)
  int compare(int L1, int R1, int L2, int R2) {
    int n1 = R1 - L1, n2 = R2 - L2;
    int n = lcp(L1, L2);
    if (n == n1 && n == n2) return 0;
    if (n == n1) return -1;
    if (n == n2) return 1;
    return (ISA[L1 + n] > ISA[L2 + n] ? 1 : -1);
  }

 private:
  void induced_sort(const vc<int>& vect, int val_range, vc<int>& SA,
                    const vc<bool>& sl, const vc<int>& lms_idx) {
    vc<int> l(val_range, 0), r(val_range, 0);
    for (int c : vect) {
      if (c + 1 < val_range) ++l[c + 1];
      ++r[c];
    }
    partial_sum(l.begin(), l.end(), l.begin());
    partial_sum(r.begin(), r.end(), r.begin());
    fill(SA.begin(), SA.end(), -1);
    for (int i = (int)lms_idx.size() - 1; i >= 0; --i)
      SA[--r[vect[lms_idx[i]]]] = lms_idx[i];
    for (int i : SA)
      if (i >= 1 && sl[i - 1]) SA[l[vect[i - 1]]++] = i - 1;
    fill(r.begin(), r.end(), 0);
    for (int c : vect) ++r[c];
    partial_sum(r.begin(), r.end(), r.begin());
    for (int k = (int)SA.size() - 1, i = SA[k]; k >= 1; --k, i = SA[k])
      if (i >= 1 && !sl[i - 1]) {
        SA[--r[vect[i - 1]]] = i - 1;
      }
  }

  vc<int> SA_IS(const vc<int>& vect, int val_range) {
    const int n = vect.size();
    vc<int> SA(n), lms_idx;
    vc<bool> sl(n);
    sl[n - 1] = false;
    for (int i = n - 2; i >= 0; --i) {
      sl[i] = (vect[i] > vect[i + 1] || (vect[i] == vect[i + 1] && sl[i + 1]));
      if (sl[i] && !sl[i + 1]) lms_idx.push_back(i + 1);
    }
    reverse(lms_idx.begin(), lms_idx.end());
    induced_sort(vect, val_range, SA, sl, lms_idx);
    vc<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size());
    for (int i = 0, k = 0; i < n; ++i)
      if (!sl[SA[i]] && SA[i] >= 1 && sl[SA[i] - 1]) {
        new_lms_idx[k++] = SA[i];
      }
    int cur = 0;
    SA[n - 1] = cur;
    for (size_t k = 1; k < new_lms_idx.size(); ++k) {
      int i = new_lms_idx[k - 1], j = new_lms_idx[k];
      if (vect[i] != vect[j]) {
        SA[j] = ++cur;
        continue;
      }
      bool flag = false;
      for (int a = i + 1, b = j + 1;; ++a, ++b) {
        if (vect[a] != vect[b]) {
          flag = true;
          break;
        }
        if ((!sl[a] && sl[a - 1]) || (!sl[b] && sl[b - 1])) {
          flag = !((!sl[a] && sl[a - 1]) && (!sl[b] && sl[b - 1]));
          break;
        }
      }
      SA[j] = (flag ? ++cur : cur);
    }
    for (size_t i = 0; i < lms_idx.size(); ++i) lms_vec[i] = SA[lms_idx[i]];
    if (cur + 1 < (int)lms_idx.size()) {
      auto lms_SA = SA_IS(lms_vec, cur + 1);
      for (size_t i = 0; i < lms_idx.size(); ++i) {
        new_lms_idx[i] = lms_idx[lms_SA[i]];
      }
    }
    induced_sort(vect, val_range, SA, sl, new_lms_idx);
    return SA;
  }

  vc<int> calc_suffix_array(const string& s, const char first = 'a',
                            const char last = 'z') {
    vc<int> vect(s.size() + 1);
    copy(begin(s), end(s), begin(vect));
    for (auto& x : vect) x -= (int)first - 1;
    vect.back() = 0;
    auto ret = SA_IS(vect, (int)last - (int)first + 2);
    ret.erase(ret.begin());
    return ret;
  }

  vc<int> calc_suffix_array(const vc<int>& s) {
    vc<int> ss = s;
    UNIQUE(ss);

    vc<int> vect(s.size() + 1);
    copy(all(s), vect.begin());
    for (auto& x : vect) x = LB(ss, x) + 1;
    vect.back() = 0;
    auto ret = SA_IS(vect, MAX(vect) + 2);
    ret.erase(ret.begin());
    return ret;
  }

  template <typename STRING>
  void calc_LCP(const STRING& s) {
    int n = s.size(), k = 0;
    ISA.resize(n);
    LCP.resize(n);
    for (int i = 0; i < n; i++) ISA[SA[i]] = i;
    for (int i = 0; i < n; i++, k ? k-- : 0) {
      if (ISA[i] == n - 1) {
        k = 0;
        continue;
      }
      int j = SA[ISA[i] + 1];
      while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
      LCP[ISA[i]] = k;
    }
    LCP.resize(n - 1);
  }
};
#line 2 "string/sort_substrings.hpp"

// dp[i][j]：S[i:i+j) の rank
// 結果のテーブルが使いにくいなら suffix tree を dfs してもらう方がよいかも
template <typename STRING>
vvc<int> sort_substrings(STRING& S, int max_len = -1) {
  int n = len(S);
  if (max_len == -1) max_len = n;
  Suffix_Array sa(S);
  auto& SA = sa.SA;
  auto& LCP = sa.LCP;
  int nxt = 0;
  vv(int, dp, n, max_len + 1, -1);
  FOR(i, len(SA)) {
    auto L = SA[i];
    FOR(k, 1, min(n - L, max_len) + 1) {
      int R = L + k;
      if (i > 0 && LCP[i - 1] >= k)
        dp[L][R - L] = dp[SA[i - 1]][k];
      else
        dp[L][R - L] = nxt++;
    }
  }
  return dp;
}
Back to top page