RT，萌新求教QAQ

#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int kMaxN(1000000);

int n(0), k(0);
int kSa[kMaxN + 5];
int kRk[kMaxN + 5];
int kTmp[kMaxN + 5];

void CalcSa(const string&);
bool CompSa(int, int);

int main(void) {
  string str;
  memset(kSa, 0, sizeof(kSa));
  memset(kRk, 0, sizeof(kRk));
  memset(kTmp, 0, sizeof(kTmp));
  ios::sync_with_stdio(false);

  cin >> str;
  n = static_cast<int>(str.size());
  CalcSa(str);

  for (int i = 0; i < n - 1; ++i)
    cout << kSa[i] + 1 << ' ';

  cout << kSa[n - 1] + 1 << endl;

  return 0;
}

void CalcSa(const string& str) {
  for (int i = 0; i < n + 1; ++i) {
    kRk[i] = str[i];
    kSa[i] = i;
  }

  for (k = 1; k < n + 1; k <<= 1) {
    sort(kSa, kSa + n, CompSa);
    kTmp[kSa[0]] = 0;

    for (int i = 0; i < n; ++i)
      kTmp[kSa[i + 1]] = kTmp[kSa[i]] + (CompSa(kSa[i], kSa[i + 1]) ? 1 : 0);

    memcpy(kRk, kTmp, sizeof(kTmp));
  }
}

bool CompSa(int x, int y) {
  if (kRk[x] == kRk[y]) {
    int x_low(x + k < n + 1 ? kRk[x + k] : -1),
        y_low(y + k < n + 1 ? kRk[y + k] : -1);
    return x_low < y_low;
  } else {
    return kRk[x] < kRk[y];
  }
}