This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// @brief Suffix Array: $O(N \log N)$
template <typename ArrayTp, typename ElemTp>
struct SuffixArray {
private:
ArrayTp s;
vector<int> cmp_s;
ElemTp dummy;
vector<int> rec, rev, lcp, cnt;
int len, sigma;
public:
// @brief dummy は、t のどの要素よりも小さい
SuffixArray(ArrayTp s_, ElemTp dummy_ = '$') : s(s_), dummy(dummy_) {
s.push_back(dummy);
len = s.size();
vector<ElemTp> seq;
for(const auto& e : s) seq.emplace_back(e);
sort(seq.begin(), seq.end());
seq.erase(unique(seq.begin(), seq.end()), seq.end());
sigma = seq.size();
for(const auto &e : s) cmp_s.emplace_back(lower_bound(seq.begin(), seq.end(), e) - seq.begin());
rec = get_Array();
rev.resize(len);
for(int i=0; i<len; i++) rev[ rec[i] ] = i;
lcp = get_LCPArray();
}
void dump_array(const vector<int> &indices,
const vector<int> &classes) const {
fprintf(stderr, "# debug\n");
fprintf(stderr, "# indices:");
for(int i=0; i<len; i++) fprintf(stderr, " %d", indices[i]);
fprintf(stderr, "\n");
fprintf(stderr, "# classes:");
for(int i=0; i<len; i++) fprintf(stderr, " %d", classes[i]);
fprintf(stderr, "\n");
}
vector<int> get_Array() {
cnt.resize(len);
vector<int> indices(len), prev_idx(len);
vector<int> classes(len), prev_cls(len);
vector<int> tmp_val(len);
// k == 0 はカウントソートのみ
for(int i=0; i<len; i++) {
cnt[ cmp_s[i] ]++;
}
for(int i=1; i<len; i++) {
cnt[i] += cnt[i-1];
}
for(int i=len-1; i>=0; i--) {
indices[ --cnt[ cmp_s[i] ] ] = i;
}
for(int i=1; i<len; i++) {
int pena = (s[ indices[i] ] != s[ indices[i-1] ]);
classes[ indices[i] ] = classes[ indices[i-1] ] + pena;
}
for(int k=0; (1 << k) < len; k++) {
swap(indices, prev_idx);
swap(classes, prev_cls);
for(int i=0; i<len; i++) {
// 後半だけソート済みにしたものを indices に代入
prev_idx[i] = prev_idx[i] - (1 << k);
if(prev_idx[i] < 0) prev_idx[i] += len;
tmp_val[i] = prev_cls[ prev_idx[i] ];
}
// 前半についてカウントソート
fill(cnt.begin(), cnt.end(), (int)0);
for(int i=0; i<len; i++) {
cnt[ tmp_val[i] ]++;
}
for(int i=1; i<len; i++) {
cnt[i] += cnt[i-1];
}
for(int i=len-1; i>=0; i--) {
indices[ --cnt[ tmp_val[i] ] ] = prev_idx[i];
}
classes[ indices[0] ] = 0;
for(int i=1; i<len; i++) {
int shift = (1 << k);
pair<int, int> pre(prev_cls[ indices[i-1] ], prev_cls[ (indices[i-1] + shift) % len ]);
pair<int, int> cur(prev_cls[ indices[i ] ], prev_cls[ (indices[i ] + shift) % len ]);
int pena = (pre != cur);
classes[ indices[i] ] = classes[ indices[i-1] ] + pena;
}
}
return indices;
}
int size() const {
return rec.size();
}
// @brief get_SA2Str: SA 配列の idx 番目は元の文字列の何番目?
int get_SA2Str(int idx) const {
assert(0 <= idx and idx < size());
return rec[idx];
}
// @brief get_Str2SA: 元の文字列の idx 番目は SA 配列の何番目?
int get_Str2SA(int idx) const {
assert(0 <= idx and idx < size());
return rev[idx];
}
// @brief get_LCP: SA 配列上の idx, idx+1 番目の要素の LCP はいくらか?
int get_LCP(int idx) const {
assert(0 <= idx and idx < size());
return lcp[idx];
}
// SA 配列上 idx 番目以降の接尾辞は、パターン文字列 p に比べて大きいか?
bool is_greater(const ArrayTp &p, int idx) const {
idx = get_SA2Str(idx);
int N = size(), M = p.size(), x, y;
for(x=idx, y=0; x<N and y<M; x++, y++) {
if(s[x] > p[y]) return true;
if(s[x] < p[y]) return false;
}
return y >= M and x < N;
}
// SA 配列上 idx 番目以降の接尾辞は、パターン文字列 p に比べて小さいか?
bool is_less(const ArrayTp &p, int idx) const {
idx = get_SA2Str(idx);
int N = size(), M = p.size(), x, y;
for(x=idx, y=0; x<N and y<M; x++, y++) {
if(s[x] < p[y]) return true;
if(s[x] > p[y]) return false;
}
return x >= N and y < M;
}
// @brief SA 配列上の、パターン文字列を超える最小インデックス: $O(|T| \log |S|)$
// SA 配列上で、p より大きくなる要素であって最小のもの (存在しなければ -1)
int binary_search_greater(const ArrayTp &p) const {
int lb = -1, ub = len;
while(ub - lb > 1) {
int mid = (ub + lb) / 2;
if(is_greater(p, mid)) ub = mid;
else lb = mid;
}
if(ub == len) return -1;
return ub;
}
// @brief SA 配列上の、パターン文字列未満最大インデックス: $O(|T| \log |S|)$
// SA 配列上で、p より小さくなる要素であって最大のもの (存在しなければ -1)
int binary_search_less(const ArrayTp &p) const {
int lb = -1, ub = len;
while(ub - lb > 1) {
int mid = (ub + lb) / 2;
if(is_less(p, mid)) lb = mid;
else ub = mid;
}
if(lb == -1) return -1;
return lb;
}
// @brief LCP (SA 配列上の i 番目と i+1 番目の最長共通接頭辞): $O(|S|)$
vector<int> get_LCPArray() {
vector<int> rank(len);
for(int i=0; i<len; i++) {
rank[ rec[i] ] = i;
}
vector<int> res(len, -1);
int cons = 0;
// 空文字列に関しては探索しない!
for(int i=0; i+1<len; i++) {
// i 文字目から始まる接尾辞に対して
// SA 配列上で直前の要素をもってくる
int pre = rec[ rank[i] - 1 ], cur = i;
while(s[cur + cons] == s[pre + cons]) cons++;
res[ rank[i] - 1 ] = cons;
cons = max<int>(0, cons - 1);
}
return res;
}
// @brief 文字列検索: $O(|T| \log |S|)$
// - パターン文字列未満になる場所を特定
// - 境界についてパターン文字列と一致するか判定
// - LCP が十分大きい限り順番に降りていく?
vector<int> match(const ArrayTp &p) const {
int t = binary_search_less(p) + 1;
int k = (t < len ? get_SA2Str(t) : len + 1);
int N = p.size();
bool match_first = (k+N <= len);
for(int i=0; i<N and match_first; i++) match_first &= (p[i] == s[k+i]);
if(!match_first) return {};
vector<int> res;
while(t < len) {
res.emplace_back(get_SA2Str(t));
if(get_LCP(t) < static_cast<int>(p.size())) break;
t++;
}
sort(res.begin(), res.end());
return res;
}
};
#line 1 "string/str_006_suffixarray.cpp"
// @brief Suffix Array: $O(N \log N)$
template <typename ArrayTp, typename ElemTp>
struct SuffixArray {
private:
ArrayTp s;
vector<int> cmp_s;
ElemTp dummy;
vector<int> rec, rev, lcp, cnt;
int len, sigma;
public:
// @brief dummy は、t のどの要素よりも小さい
SuffixArray(ArrayTp s_, ElemTp dummy_ = '$') : s(s_), dummy(dummy_) {
s.push_back(dummy);
len = s.size();
vector<ElemTp> seq;
for(const auto& e : s) seq.emplace_back(e);
sort(seq.begin(), seq.end());
seq.erase(unique(seq.begin(), seq.end()), seq.end());
sigma = seq.size();
for(const auto &e : s) cmp_s.emplace_back(lower_bound(seq.begin(), seq.end(), e) - seq.begin());
rec = get_Array();
rev.resize(len);
for(int i=0; i<len; i++) rev[ rec[i] ] = i;
lcp = get_LCPArray();
}
void dump_array(const vector<int> &indices,
const vector<int> &classes) const {
fprintf(stderr, "# debug\n");
fprintf(stderr, "# indices:");
for(int i=0; i<len; i++) fprintf(stderr, " %d", indices[i]);
fprintf(stderr, "\n");
fprintf(stderr, "# classes:");
for(int i=0; i<len; i++) fprintf(stderr, " %d", classes[i]);
fprintf(stderr, "\n");
}
vector<int> get_Array() {
cnt.resize(len);
vector<int> indices(len), prev_idx(len);
vector<int> classes(len), prev_cls(len);
vector<int> tmp_val(len);
// k == 0 はカウントソートのみ
for(int i=0; i<len; i++) {
cnt[ cmp_s[i] ]++;
}
for(int i=1; i<len; i++) {
cnt[i] += cnt[i-1];
}
for(int i=len-1; i>=0; i--) {
indices[ --cnt[ cmp_s[i] ] ] = i;
}
for(int i=1; i<len; i++) {
int pena = (s[ indices[i] ] != s[ indices[i-1] ]);
classes[ indices[i] ] = classes[ indices[i-1] ] + pena;
}
for(int k=0; (1 << k) < len; k++) {
swap(indices, prev_idx);
swap(classes, prev_cls);
for(int i=0; i<len; i++) {
// 後半だけソート済みにしたものを indices に代入
prev_idx[i] = prev_idx[i] - (1 << k);
if(prev_idx[i] < 0) prev_idx[i] += len;
tmp_val[i] = prev_cls[ prev_idx[i] ];
}
// 前半についてカウントソート
fill(cnt.begin(), cnt.end(), (int)0);
for(int i=0; i<len; i++) {
cnt[ tmp_val[i] ]++;
}
for(int i=1; i<len; i++) {
cnt[i] += cnt[i-1];
}
for(int i=len-1; i>=0; i--) {
indices[ --cnt[ tmp_val[i] ] ] = prev_idx[i];
}
classes[ indices[0] ] = 0;
for(int i=1; i<len; i++) {
int shift = (1 << k);
pair<int, int> pre(prev_cls[ indices[i-1] ], prev_cls[ (indices[i-1] + shift) % len ]);
pair<int, int> cur(prev_cls[ indices[i ] ], prev_cls[ (indices[i ] + shift) % len ]);
int pena = (pre != cur);
classes[ indices[i] ] = classes[ indices[i-1] ] + pena;
}
}
return indices;
}
int size() const {
return rec.size();
}
// @brief get_SA2Str: SA 配列の idx 番目は元の文字列の何番目?
int get_SA2Str(int idx) const {
assert(0 <= idx and idx < size());
return rec[idx];
}
// @brief get_Str2SA: 元の文字列の idx 番目は SA 配列の何番目?
int get_Str2SA(int idx) const {
assert(0 <= idx and idx < size());
return rev[idx];
}
// @brief get_LCP: SA 配列上の idx, idx+1 番目の要素の LCP はいくらか?
int get_LCP(int idx) const {
assert(0 <= idx and idx < size());
return lcp[idx];
}
// SA 配列上 idx 番目以降の接尾辞は、パターン文字列 p に比べて大きいか?
bool is_greater(const ArrayTp &p, int idx) const {
idx = get_SA2Str(idx);
int N = size(), M = p.size(), x, y;
for(x=idx, y=0; x<N and y<M; x++, y++) {
if(s[x] > p[y]) return true;
if(s[x] < p[y]) return false;
}
return y >= M and x < N;
}
// SA 配列上 idx 番目以降の接尾辞は、パターン文字列 p に比べて小さいか?
bool is_less(const ArrayTp &p, int idx) const {
idx = get_SA2Str(idx);
int N = size(), M = p.size(), x, y;
for(x=idx, y=0; x<N and y<M; x++, y++) {
if(s[x] < p[y]) return true;
if(s[x] > p[y]) return false;
}
return x >= N and y < M;
}
// @brief SA 配列上の、パターン文字列を超える最小インデックス: $O(|T| \log |S|)$
// SA 配列上で、p より大きくなる要素であって最小のもの (存在しなければ -1)
int binary_search_greater(const ArrayTp &p) const {
int lb = -1, ub = len;
while(ub - lb > 1) {
int mid = (ub + lb) / 2;
if(is_greater(p, mid)) ub = mid;
else lb = mid;
}
if(ub == len) return -1;
return ub;
}
// @brief SA 配列上の、パターン文字列未満最大インデックス: $O(|T| \log |S|)$
// SA 配列上で、p より小さくなる要素であって最大のもの (存在しなければ -1)
int binary_search_less(const ArrayTp &p) const {
int lb = -1, ub = len;
while(ub - lb > 1) {
int mid = (ub + lb) / 2;
if(is_less(p, mid)) lb = mid;
else ub = mid;
}
if(lb == -1) return -1;
return lb;
}
// @brief LCP (SA 配列上の i 番目と i+1 番目の最長共通接頭辞): $O(|S|)$
vector<int> get_LCPArray() {
vector<int> rank(len);
for(int i=0; i<len; i++) {
rank[ rec[i] ] = i;
}
vector<int> res(len, -1);
int cons = 0;
// 空文字列に関しては探索しない!
for(int i=0; i+1<len; i++) {
// i 文字目から始まる接尾辞に対して
// SA 配列上で直前の要素をもってくる
int pre = rec[ rank[i] - 1 ], cur = i;
while(s[cur + cons] == s[pre + cons]) cons++;
res[ rank[i] - 1 ] = cons;
cons = max<int>(0, cons - 1);
}
return res;
}
// @brief 文字列検索: $O(|T| \log |S|)$
// - パターン文字列未満になる場所を特定
// - 境界についてパターン文字列と一致するか判定
// - LCP が十分大きい限り順番に降りていく?
vector<int> match(const ArrayTp &p) const {
int t = binary_search_less(p) + 1;
int k = (t < len ? get_SA2Str(t) : len + 1);
int N = p.size();
bool match_first = (k+N <= len);
for(int i=0; i<N and match_first; i++) match_first &= (p[i] == s[k+i]);
if(!match_first) return {};
vector<int> res;
while(t < len) {
res.emplace_back(get_SA2Str(t));
if(get_LCP(t) < static_cast<int>(p.size())) break;
t++;
}
sort(res.begin(), res.end());
return res;
}
};