tests/yosupo/suffix-array.test.cpp

View this file on GitHub
Last update: 2023-02-27 10:03:35-03:00
Problem: https://judge.yosupo.jp/problem/suffixarray

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/suffixarray"

#include <bits/stdc++.h>
#include "SuffixArray.cpp"
#define int long long
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ms(v, x) memset((v), (x), sizeof(v))
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define iopt ios::sync_with_stdio(false); cin.tie(0)
#define untie(p, a, b) decltype(p.first) a = p.first, decltype(p.second) b = p.second
 
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int power(int x, int p, int MOD) {
    if(p == 0) return 1%MOD;
    if(p == 1) return x%MOD;
    int res = power(x, p/2, MOD);
    res = (long long)res*res%MOD;
    if(p&1) res = (long long)res*x%MOD;
    return res;
}
 
typedef pair<int, int> ii;
typedef long double LD;
typedef vector<int> vi;

int32_t main(){
  iopt;
  string s; cin >> s;

  lib::SuffixArray<char> sa(s);

  for(int i = 0; i < s.size(); i++) cout << sa[i] << " ";
  cout << endl;
}

#line 1 "tests/yosupo/suffix-array.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/suffixarray"

#include <bits/stdc++.h>
#line 1 "SuffixArray.cpp"


#line 4 "SuffixArray.cpp"

namespace lib {
using namespace std;
template<typename C>
struct SuffixArray {
  int n, block;
  vector<C> s;
  vector<int> sa, rnk, tmp, aux, lcp_;
  vector<vector<int>> T;

  void init(int h) {
    h = max(h, n);
    sa = vector<int>(h+3), rnk = vector<int>(h+3),
      tmp = vector<int>(h+3), aux = vector<int>(h+3),
      lcp_ = vector<int>(h+3);
    T = vector<vector<int>>(n + 3, vector<int>(__lg(n) + 1));
  }

  SuffixArray(vector<C> s_) : s(s_), n(s_.size()) { build(); }
  SuffixArray(string s_) {
    s = vector<C>(s_.size());
    n = s_.size();
    for(int i = 0; i < n; i++) s[i] = s_[i];
    build();
  }

  bool suffix_cmp(int i, int j) {
    if (rnk[i] != rnk[j]) return rnk[i] < rnk[j];
    i += block, j += block;
    if (i >= n) i -= n;
    if (j >= n) j -= n;
    return rnk[i] < rnk[j];
  }
  void suffix_sort(int h) {
    for (int i = 0; i < n; i++) {
      aux[i] = sa[i] - block;
      if (aux[i] < 0) aux[i] += n;
    }
    for (int i = 0; i < h; i++) tmp[i] = 0;
    for (int i = 0; i < n; i++) tmp[rnk[aux[i]]]++;
    for (int i = 0; i < h - 1; i++) tmp[i + 1] += tmp[i];
    for (int i = n - 1; i >= 0; i--) sa[--tmp[rnk[aux[i]]]] = aux[i];
    tmp[0] = 0;
    for (int i = 0; i < n - 1; i++) tmp[i + 1] = tmp[i] + suffix_cmp(sa[i], sa[i + 1]);
    for (int i = 0; i < n; i++) rnk[sa[i]] = tmp[i];
  }
  void build() {
    n++; // consider additional '\0' character
    s.push_back(0);
    int h = (int)(*max_element(s.begin(), s.end())) + 1;
    init(h);
    for (int i = 0; i < n; i++) sa[i] = i, rnk[i] = s[i], tmp[i] = 0;
    block = 0;
    suffix_sort(h);
    for (block = 1; tmp[n - 1] != n - 1; block *= 2) suffix_sort(tmp[n - 1] + 1);
    n--;
    sa.erase(sa.begin());
    build_lcp_();
  }

  void build_lcp_() {
		for (int i = 0; i < n; i++) rnk[sa[i]] = i, lcp_[i] = 0;
		int last = 0; // last lcp_
		for (int i = 0; i < n; i++, last = max(lcp_[rnk[i - 1]] - 1, 0)) {
			if (rnk[i] == n - 1) continue;
			int j = sa[rnk[i] + 1]; // next suffix pos in suffix array
			while (i + last < n && j + last < n && s[i + last] == s[j + last]) last++;
			lcp_[rnk[i]] = last;
		}

		for(int i = 0; i < n; i++)
			T[i][0] = lcp_[i];
		for(int j = 1; j < 20; j++){
			for(int i = 0; i+(1<<j) <= n; i++){
				T[i][j] = min(T[i][j-1], T[i+(1<<(j-1))][j-1]);
			}
		}
	}

  int lcp(int i, int j){
		if(i > j) swap(i,j);
		if(i == j) return n-sa[i];
    if(j == n) return 0;

		j--;
		int k = __builtin_clz(1) - __builtin_clz(j-i+1);
		return min(T[i][k], T[j-(1<<k)+1][k]);
	}

  int operator[](int i) const {
    return sa[i];
  }

  int length(int i) const {
    return n - sa[i];
  }

  int lcp(int i) const {
    return lcp_[i];
  }

  pair<int,int> range(int i, int sz){
    pair<int, int> res;
    {
      int l = 0, r = i+1;
      while(l < r){
        int mid = (l+r)/2;
        if(lcp(mid, i) >= sz) r = mid;
        else l = mid+1;
      }
      res.first = l;
    }
    {
      int l = i, r = n-1;
      while(l < r){
        int mid = (l+r+1)/2;
        if(lcp(mid, i) >= sz) l = mid;
        else r = mid-1;
      }
      res.second = l;
    }
    return res;
  }

  pair<int, int> range(int i) {
    return range(i, length(i));
  }
};
} // namespace lib


#line 5 "tests/yosupo/suffix-array.test.cpp"
#define int long long
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ms(v, x) memset((v), (x), sizeof(v))
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define iopt ios::sync_with_stdio(false); cin.tie(0)
#define untie(p, a, b) decltype(p.first) a = p.first, decltype(p.second) b = p.second
 
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int power(int x, int p, int MOD) {
    if(p == 0) return 1%MOD;
    if(p == 1) return x%MOD;
    int res = power(x, p/2, MOD);
    res = (long long)res*res%MOD;
    if(p&1) res = (long long)res*x%MOD;
    return res;
}
 
typedef pair<int, int> ii;
typedef long double LD;
typedef vector<int> vi;

int32_t main(){
  iopt;
  string s; cin >> s;

  lib::SuffixArray<char> sa(s);

  for(int i = 0; i < s.size(); i++) cout << sa[i] << " ";
  cout << endl;
}