代码

#ifndef LOCAL
#define NDEBUG
#endif
#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <initializer_list>
#include <iostream>
#include <memory>
#include <queue>
#include <random>
#include <vector>

void SA_IS(const int *s, int *SA, int n, int K) {
  // s 为字符串数组[0..n-1] 必须保证 s[n-1]=0 且为最小值
  // SA 为存储后缀数组[0..n-1]
  // n 为字符串长度
  // K 为值域

  bool *t = new bool[n]; // 类型数组
  int *bkt = new int[K]; // 桶
  int *bkt_l = new int[K];
  int *bkt_r = new int[K];
  int n1 = 0; // LMS-后缀的数量
  int *p1;    //按出现顺序存储所有 LMS-后缀的索引

#define is_S_type(x) (t[x])
#define is_L_type(x) (!t[x])
#define is_LMS_type(x) (is_S_type(x) && x != 0 && is_L_type(x - 1))

  // 预处理每一个后缀的类型
  t[n - 1] = true; // 0 为 S-型后缀且为 LMS-型后缀
  for (int i = n - 2; i >= 0; --i) {
    t[i] = (s[i] < s[i + 1] || (is_S_type(i + 1) && s[i] == s[i + 1]));
    n1 += is_LMS_type(i + 1); // s[0] 必然不是 LMS-型后缀，不会影响
  }

  // 预处理桶的边界
  for (int i = 0; i != K; ++i) bkt[i] = 0;
  for (int i = 0; i != n; ++i) ++bkt[s[i]];
  for (int i = 0, sum = 0; i != K; ++i) sum += bkt[i], bkt_r[i] = sum, bkt_l[i] = sum - bkt[i];

#define induced_sort()                                                                             \
  do {                                                                                             \
    for (int i = 0; i != K; ++i) bkt[i] = bkt_l[i];                                                \
    for (int i = 0, j; i != n; ++i)                                                                \
      if ((j = SA[i] - 1) >= 0 && is_L_type(j)) SA[bkt[s[j]]++] = j;                               \
    for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i];                                                \
    for (int i = n - 1, j; i >= 0; --i)                                                            \
      if ((j = SA[i] - 1) >= 0 && is_S_type(j)) SA[--bkt[s[j]]] = j;                               \
  } while (0)

  // 将所有 LMS-后缀放入 SA 对应桶的末尾并诱导排序
  p1 = new int[n1];
  for (int i = 0, j = 0; i != n; ++i) {
    SA[i] = -1;
    if (is_LMS_type(i)) p1[j++] = i;
  }
  for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i];
  for (int i = n1 - 1; i >= 0; --i) SA[--bkt[s[p1[i]]]] = p1[i];
  induced_sort();

  int *s1 = new int[n1];  // 新的字符串
  int *SA1 = new int[n1]; // 存储新的字符串排的后缀数组
  for (int i = 0, j = 0; i != n; ++i)
    if (is_LMS_type(SA[i])) SA1[j++] = SA[i]; // 存储 LMS-子串的相对顺序
  int name = 0;
  // 对所有 LMS-子串命名
  for (int i = 0, prev = -1; i != n1; ++i) {
    int pos = SA1[i];
    for (int j = 0;; ++j) // 无需设置范围，因为 s[n-1]=0 为最小值且不会出现在其余位置
      if (prev == -1 || s[pos + j] != s[prev + j] || is_S_type(pos + j) != is_S_type(prev + j)) {
        prev = pos, ++name;
        break;
      } else if (j != 0 && (is_LMS_type(pos + j) || is_LMS_type(prev + j))) // 到末尾了停止比较
        break;
    SA[pos] = name - 1; // 利用 SA 暂时存储新字符串的 name
  }
  for (int i = 0; i != n1; ++i) s1[i] = SA[p1[i]];

  if (name != n1)
    SA_IS(s1, SA1, n1, name);
  else
    for (int i = 0; i != n1; ++i) SA1[s1[i]] = i;

  for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i];
  for (int i = 0; i != n; ++i) SA[i] = -1;
  for (int i = n1 - 1; i >= 0; --i) SA[--bkt[s[p1[SA1[i]]]]] = p1[SA1[i]];
  induced_sort();

  delete[] SA1;
  delete[] s1;
  delete[] p1;
  delete[] bkt_r;
  delete[] bkt_l;
  delete[] bkt;
  delete[] t;

#undef is_S_type
#undef is_L_type
#undef is_LMS_type
#undef induced_sort
}

std::vector<int> get_sa(const std::string &s) {
  int n = s.size();
  std::vector<int> SA(n + 1), s_cpy(n + 1);
  std::copy_n(s.begin(), n, s_cpy.begin());
  s_cpy.back() = 0;
  SA_IS(s_cpy.data(), SA.data(), n + 1, 128);
  SA.erase(SA.begin());
  return SA;
}

void sa2height(const std::string &s, std::vector<int> &SA) {
  int n = s.size();
  std::vector<int> rk(n);
  for (int i = 0; i != n; ++i) rk[SA[i]] = i;
  for (int i = 0, h = 0; i != n; ++i) {
    int rki = rk[i];
    if (rki > 0) {
      for (int j = SA[rki - 1]; i + h < n && j + h < n && s[i + h] == s[j + h]; ++h) {
      }
      SA[rki - 1] = h;
      if (h > 0) --h;
    }
  }
  SA.pop_back();
}

struct IO {
public:
  IO() : s(a), t(b) {
    /* make sure that the buffer size is big enough. */
#ifdef LOCAL
    std::freopen("..\\in", "r", stdin), std::freopen("..\\out", "w", stdout);
#endif
    a[e = std::fread(a, 1, sizeof a, stdin)] = '\0';
  }
  ~IO() { std::fwrite(b, 1, t - b, stdout); }
  operator bool() const { return s - a <= e; }
  IO &operator<<(char x) { return *t++ = x, *this; }
  IO &operator<<(const char *x) {
    while (*x != '\0') *t++ = *x++;
    return *this;
  }
  IO &operator>>(char *x) {
    while (s - a <= e && *s != '\n' && *s != '\r' && *s != '\t' && *s != ' ') *x++ = *s++;
    return *this;
  }
  template <typename T> std::enable_if_t<std::is_integral_v<T>, IO &> operator>>(T &x) {
    x = 0;
    if constexpr (std::is_signed_v<T>) {
      while (s - a <= e && *s != '-' && (*s < '0' || *s > '9')) ++s;
      bool m = (*s == '-' && ++s);
      if (m)
        while (*s >= '0' && *s <= '9') x = x * 10 - (*s++ - '0');
      else
        while (*s >= '0' && *s <= '9') x = x * 10 + (*s++ - '0');
    } else {
      while (s - a <= e && (*s < '0' || *s > '9')) ++s;
      while (*s >= '0' && *s <= '9') x = x * 10 + (*s++ - '0');
    }
    return *this;
  }
  template <typename T> std::enable_if_t<std::is_integral_v<T>, IO &> operator<<(T x) {
    static char c[32], *i;
    i = c;
    if (x == 0) return *t++ = '0', *this;
    if constexpr (std::is_signed_v<T>) {
      if (x < 0) {
        *t++ = '-';
        while (x != 0) {
          T y = x / 10;
          *i++ = y * 10 - x + '0', x = y;
        }
      } else {
        while (x != 0) {
          T y = x / 10;
          *i++ = x - y * 10 + '0', x = y;
        }
      }
    } else {
      while (x != 0) {
        T y = x / 10;
        *i++ = x - y * 10 + '0', x = y;
      }
    }
    while (i != c) *t++ = *--i;
    return *this;
  }

private:
  static inline char a[1 << 25], b[1 << 25];
  char *s, *t;
  int e;
} io;

char s[100005];

int main() {
  io >> s;
  std::string s_cpy(s);
  auto SA = get_sa(s_cpy);
  for (auto i : SA) io << i + 1 << ' ';
  io << '\n';
  sa2height(s_cpy, SA);
  for (auto i : SA) io << i << ' ';
  return 0;
}

评测结果