test/string/SuffixArray.test.cpp

• View this file on GitHub
• Last update: 2026-07-24 16:03:15+09:00
• Problem: https://judge.yosupo.jp/problem/suffixarray

Depends on

• Suffix Array (src/string/SuffixArray.hpp)
• test/template.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/suffixarray
#include "test/template.hpp"
#include "src/string/SuffixArray.hpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);
   string S;
   cin >> S;
   const ll N = sz(S);
   auto [sa, lcp] = SA(S);
   assert(sa.size() == N);
   assert(lcp.size() == N - 1);
   rep(i, 0, N) cout << sa[i] << " \n"[i + 1 == N];
}

#line 1 "test/string/SuffixArray.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/suffixarray
#line 1 "test/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
template<class T> using V = vector<T>;
#define rep(i, a, b) for(ll i = a; i < (b); i++)
#define each(i, a) for(auto&& i : a)
#define all(a) begin(a), end(a)
#define sz(a) ssize(a)
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
#line 1 "src/string/SuffixArray.hpp"
// returns pair{sa, lcp}
// sa 長さ n : s[sa[0]:] < s[sa[1]:] < … < s[sa[n-1]:]
// lcp 長さ n-1 : lcp[i] = LCP(s[sa[i]:], s[sa[i+1]:])
// O(n log n) time
auto SA(auto s) {  // string or vector
   // assert(s.size() >= 1);
   ll n = sz(s);
   V<ll> sa(n), r(n + 1), x(n), y(n + 1), c(n + 1);
   rep(i, 0, n) sa[i] = i;
   ranges::sort(sa, {}, [&](ll i) { return s[i]; });
   r[sa[0]] = 1;
   rep(i, 1, n) r[sa[i]] = r[sa[i - 1]] + (s[sa[i - 1]] != s[sa[i]]);
   for(ll k = 1; k < n && r[sa.back()] < n; k *= 2) {
      ll p = 0;
      rep(i, n - k, n) x[p++] = i;
      each(i, sa) if(i >= k) x[p++] = i - k;
      ranges::fill(c, 0);
      each(i, x) c[r[i]]++;
      rep(i, 0, n) c[i + 1] += c[i];
      each(i, x | views::reverse) sa[--c[r[i]]] = i;
      y[sa[0]] = 1;
      rep(i, 1, n) {
         ll a = sa[i - 1], b = sa[i];
         y[b] = y[a] + (r[a] != r[b] || r[min(a + k, n)] != r[min(b + k, n)]);
      }
      swap(r, y);
   }
   // if you need lcp array
   x.pop_back();
   ll h = 0;
   rep(i, 0, n) {
      ll p = r[i] - 1;
      if(p == n - 1) {
         h = 0;
         continue;
      }
      ll j = sa[p + 1];
      while(i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
      x[p] = h;
      if(h) h--;
   }
   return pair{sa, x};
}
#line 4 "test/string/SuffixArray.test.cpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);
   string S;
   cin >> S;
   const ll N = sz(S);
   auto [sa, lcp] = SA(S);
   assert(sa.size() == N);
   assert(lcp.size() == N - 1);
   rep(i, 0, N) cout << sa[i] << " \n"[i + 1 == N];
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_same_00	AC	100 ms	31 MB
g++	all_same_01	AC	107 ms	31 MB
g++	all_same_02	AC	103 ms	31 MB
g++	all_same_03	AC	100 ms	31 MB
g++	all_same_04	AC	103 ms	31 MB
g++	almost_single_00	AC	99 ms	32 MB
g++	almost_single_01	AC	108 ms	32 MB
g++	almost_single_02	AC	105 ms	32 MB
g++	almost_single_03	AC	110 ms	32 MB
g++	almost_single_04	AC	99 ms	32 MB
g++	almost_single_05	AC	102 ms	32 MB
g++	binary_carry_00	AC	420 ms	31 MB
g++	binary_carry_01	AC	474 ms	31 MB
g++	example_00	AC	3 ms	4 MB
g++	example_01	AC	2 ms	4 MB
g++	example_02	AC	2 ms	4 MB
g++	example_03	AC	2 ms	4 MB
g++	fib_str_00	AC	145 ms	32 MB
g++	fib_str_01	AC	106 ms	24 MB
g++	fib_str_02	AC	98 ms	23 MB
g++	fib_str_03	AC	88 ms	21 MB
g++	fib_str_04	AC	161 ms	31 MB
g++	hack_00	AC	3 ms	4 MB
g++	hack_01	AC	2 ms	4 MB
g++	hack_02	AC	2 ms	4 MB
g++	max_random_00	AC	93 ms	31 MB
g++	max_random_01	AC	81 ms	31 MB
g++	max_random_02	AC	82 ms	31 MB
g++	max_random_03	AC	82 ms	31 MB
g++	max_random_04	AC	82 ms	31 MB
g++	near_power_of_2_max_random_00	AC	46 ms	18 MB
g++	near_power_of_2_max_random_01	AC	45 ms	18 MB
g++	near_power_of_2_max_same_00	AC	49 ms	18 MB
g++	near_power_of_2_max_same_01	AC	52 ms	18 MB
g++	one_00	AC	3 ms	4 MB
g++	random_00	AC	64 ms	25 MB
g++	random_01	AC	77 ms	30 MB
g++	random_02	AC	11 ms	6 MB
g++	random_03	AC	71 ms	28 MB
g++	random_04	AC	48 ms	19 MB
g++	small_random_00	AC	3 ms	4 MB
g++	small_random_01	AC	2 ms	4 MB
g++	small_random_02	AC	2 ms	4 MB
g++	small_random_03	AC	2 ms	4 MB
g++	small_random_04	AC	2 ms	4 MB
g++	small_random_05	AC	2 ms	4 MB
g++	small_random_06	AC	2 ms	4 MB
g++	small_random_07	AC	2 ms	4 MB
g++	small_random_08	AC	2 ms	4 MB
g++	small_random_09	AC	2 ms	4 MB

Back to top page