Function RawSkew

libs/base/suffix_array.cpp:97–234

// Array Construction" by Juha K¨arkk¨ainen and Peter Sanders.
template <typename S>
void RawSkew(size_t n, size_t maxValue, S const & s, size_t * sa)
{
  size_t constexpr kInvalidId = std::numeric_limits<size_t>::max();

  if (n == 0)
    return;

  if (n == 1)
  {
    sa[0] = 0;
    return;
  }

  size_t const n0 = (n + 2) / 3;  // Number of =0 (mod 3) suffixes.
  size_t const n1 = (n + 1) / 3;  // Number of =1 (mod 3) suffixes.
  size_t const n2 = n / 3;        // Number of =2 (mod 3) suffixes.

  size_t const n02 = n0 + n2;

  size_t const fake1 = n0 != n1 ? 1 : 0;

  // The total number of =1 (mod 3) suffixes (including the fake one)
  // is the same as the number of =0 (mod 3) suffixes.
  ASSERT_EQUAL(n1 + fake1, n0, ());
  ASSERT_EQUAL(fake1, static_cast<uint32_t>(n % 3 == 1), ());

  // Generate positions of =(1|2) (mod 3) suffixes.
  std::vector<size_t> s12(n02 + 3);
  std::vector<size_t> sa12(n02 + 3);

  // (n0 - n1) is needed in case when n == 0 (mod 3).  We need a fake
  // =1 (mod 3) suffix for proper sorting of =0 (mod 3) suffixes.
  // Therefore we force here that the number of =1 (mod 3) suffixes
  // should be the same as the number of =0 (mod 3) suffixes. That's
  // why we need that s[n] = s[n + 1] = s[n + 2] = 0.
  for (size_t i = 0, j = 0; i < n + fake1; ++i)
    if (i % 3 != 0)
      s12[j++] = i;

  // Following three lines perform a stable sorting of all triples
  // <s[i], s[i + 1], s[i + 2]> where i =(1|2) (mod 3), including
  // possible fake1 suffix. Final order of these triples is written to
  // |sa12|.
  RadixSort(n02, s12.data(), maxValue + 1, MakeSlice(s, 2), sa12.data());
  RadixSort(n02, sa12.data(), maxValue + 1, MakeSlice(s, 1), s12.data());
  RadixSort(n02, s12.data(), maxValue + 1, s, sa12.data());

  // Generate lexicographic names for all =(1|2) (mod 3) triples.
  size_t name = 0;
  size_t c0 = kInvalidId;
  size_t c1 = kInvalidId;
  size_t c2 = kInvalidId;
  for (size_t i = 0; i < n02; ++i)
  {
    auto const pos = sa12[i];
    if (s[pos] != c0 || s[pos + 1] != c1 || s[pos + 2] != c2)
    {
      c0 = s[pos];