#ifndef AFSTR_SUFFIX_ARRAY
#define AFSTR_SUFFIX_ARRAY
#include <algorithm>
#include <string>
#include <vector>
#include "../data_structure/sparse-table.hpp"
class SuffixArray {
private:
int n;
std::string s; // internal is 1-index, access is 0-indexed.
SparseTable<MinInfo<int>> ST;
std::vector<int> sa, rnk, old, h;
public:
SuffixArray(std::string S) : n(S.size()), s(S) {
const int m = n + 1;
s.insert(s.begin(), ' '), sa.assign(m, 0);
rnk.assign(m, 0), old.assign(m, 0), h.assign(m, 0);
for (int i = 1; i <= n; i++) sa[i] = i, rnk[i] = s[i];
for (int w = 1; w < n; w *= 2) {
std::copy(rnk.begin(), rnk.end(), old.begin());
auto cmp = [&](int x, int y) {
if (old[x] != old[y]) return old[x] < old[y];
if (y + w > n) return false;
if (x + w > n) return true;
return old[x + w] < old[y + w];
};
std::sort(std::next(sa.begin()), sa.end(), cmp);
for (int i = 1; i <= n; i++) {
rnk[sa[i]] = rnk[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
}
if (rnk[sa[n]] == n) break;
}
for (int i = 1, k = 0; i <= n; i++) {
if (rnk[i] == 0) continue;
if (k != 0) k--;
while (std::max(i, sa[rnk[i] - 1]) <= n - k &&
s[i + k] == s[sa[rnk[i] - 1] + k]) {
k++;
}
h[rnk[i]] = k;
}
ST.init(h);
}
const std::vector<int> get_h(void) { return h; }
const std::vector<int> get_sa(void) { return sa; }
const std::vector<int> get_rnk(void) { return rnk; }
inline int lcp(int i, int j) { // 0-indexed !
i = rnk[i + 1], j = rnk[j + 1];
if (i > j) std::swap(i, j);
return i == j ? n - i : ST.query(i + 1, j).val;
}
};
#endif
#line 1 "src/alfred/string/suffix-array.hpp"
#include <algorithm>
#include <string>
#include <vector>
#line 1 "src/alfred/data_structure/sparse-table.hpp"
#include <limits>
#include <numeric>
#line 7 "src/alfred/data_structure/sparse-table.hpp"
template <class T>
struct MaxInfo {
T val;
MaxInfo(void) { val = std::numeric_limits<T>::min(); }
template <class InitT>
MaxInfo(InitT x) { val = x; }
MaxInfo operator+(MaxInfo &x) {
return {std::max(val, x.val)};
}
};
template <class T>
struct MinInfo {
T val;
MinInfo(void) { val = std::numeric_limits<T>::max(); }
template <class InitT>
MinInfo(InitT x) { val = x; }
MinInfo operator+(MinInfo &x) {
return {std::min(val, x.val)};
}
};
template <class T>
struct GcdInfo {
T val;
GcdInfo(void) { val = T(); }
template <class InitT>
GcdInfo(InitT x) { val = x; }
GcdInfo operator+(GcdInfo &x) {
#if __cplusplus >= 201703L
return {std::gcd(x.val, val)};
#else
return {__gcd(x.val, val)};
#endif
}
};
template <class T>
class SparseTable {
private:
int n;
std::vector<std::vector<T>> ST;
public:
SparseTable(void) {}
SparseTable(int N) : n(N), ST(N, std::vector<T>(std::__lg(N) + 1)) {}
template <class InitT>
SparseTable(std::vector<InitT> &_init) : SparseTable(_init.size()) { init(_init, true); }
template <class InitT>
inline void init(std::vector<InitT> &_init, bool internal = false) {
if (!internal) {
n = _init.size();
ST.assign(n, std::vector<T>(std::__lg(n) + 1));
}
for (int i = 0; i < n; i++) ST[i][0] = T(_init[i]);
for (int i = 1; (1 << i) <= n; i++) {
for (int j = 0; j + (1 << i) - 1 < n; j++) {
ST[j][i] = ST[j][i - 1] + ST[j + (1 << (i - 1))][i - 1];
}
}
}
inline T query(int l, int r) { // 0 based
if (l > r) return T();
int w = std::__lg(r - l + 1);
return ST[l][w] + ST[r - (1 << w) + 1][w];
}
inline T disjoint_query(int l, int r) {
if (l > r) return T();
T ans = T();
for (int i = std::__lg(r - l + 1); i >= 0; i--) {
if ((1 << i) <= r - l + 1) {
ans = ans + ST[l][i];
l += 1 << i;
}
}
return ans;
}
};
#line 9 "src/alfred/string/suffix-array.hpp"
class SuffixArray {
private:
int n;
std::string s; // internal is 1-index, access is 0-indexed.
SparseTable<MinInfo<int>> ST;
std::vector<int> sa, rnk, old, h;
public:
SuffixArray(std::string S) : n(S.size()), s(S) {
const int m = n + 1;
s.insert(s.begin(), ' '), sa.assign(m, 0);
rnk.assign(m, 0), old.assign(m, 0), h.assign(m, 0);
for (int i = 1; i <= n; i++) sa[i] = i, rnk[i] = s[i];
for (int w = 1; w < n; w *= 2) {
std::copy(rnk.begin(), rnk.end(), old.begin());
auto cmp = [&](int x, int y) {
if (old[x] != old[y]) return old[x] < old[y];
if (y + w > n) return false;
if (x + w > n) return true;
return old[x + w] < old[y + w];
};
std::sort(std::next(sa.begin()), sa.end(), cmp);
for (int i = 1; i <= n; i++) {
rnk[sa[i]] = rnk[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
}
if (rnk[sa[n]] == n) break;
}
for (int i = 1, k = 0; i <= n; i++) {
if (rnk[i] == 0) continue;
if (k != 0) k--;
while (std::max(i, sa[rnk[i] - 1]) <= n - k &&
s[i + k] == s[sa[rnk[i] - 1] + k]) {
k++;
}
h[rnk[i]] = k;
}
ST.init(h);
}
const std::vector<int> get_h(void) { return h; }
const std::vector<int> get_sa(void) { return sa; }
const std::vector<int> get_rnk(void) { return rnk; }
inline int lcp(int i, int j) { // 0-indexed !
i = rnk[i + 1], j = rnk[j + 1];
if (i > j) std::swap(i, j);
return i == j ? n - i : ST.query(i + 1, j).val;
}
};
src/alfred/string/suffix-array.hpp