一开始写的方便理解的版本：

#include<cstdio>
#include<cstring>

const int MAX_LEN = 1e6 + 5;

class SuffixArray {
 private:
  enum type_t{L = 0, S};
  bool isLMS(type_t *type, int loc) {
    if(loc <= 0) return false;
    if(type[loc] != S) return false;
    if(type[loc - 1] != L) return false;
    return true;
  }
  template<typename T>
  bool sameLMS(T str, type_t *type, int i, int j) {
    if(i == -1 || j == -1) return false;
    int k = -1;
    while(true) {
      ++k;
      if(str[i + k] != str[j + k]) return false;
      if(type[i + k] != type[j + k]) return false;
      if(k == 0) continue;
      if(isLMS(type, i + k) != isLMS(type, j + k)) return false;
      if(isLMS(type, i + k)) break;
    }
    return true;
  }
  template<typename T>
  void inducedSort(T str, int len, int sigma, type_t *type, int *LMS, int LMSSize) {
    int *bucket = new int[sigma];
    int *buf = new int[sigma];
    memset(sa, -1, sizeof(sa[0]) * len);
    memset(bucket, 0, sizeof(bucket[0]) * sigma);
    for(int i = 0; i < len; ++i) {
      ++bucket[str[i]];
    }
    buf[0] = bucket[0];
    for(int i = 1; i < sigma; ++i) {
      buf[i] = buf[i - 1] + bucket[i];
    }
    for(int i = LMSSize - 1; i >= 0; --i) {
      sa[--buf[str[LMS[i]]]] = LMS[i];
    }

    buf[0] = 0;
    for(int i = 1; i < sigma; ++i) {
      buf[i] = buf[i - 1] + bucket[i - 1];
    }
    for(int i = 0; i < len; ++i) {
      if(sa[i] <= 0) continue;
      if(type[sa[i] - 1] != L) continue;
      sa[buf[str[sa[i] - 1]]++] = sa[i] - 1;
    }

    buf[0] = bucket[0];
    for(int i = 1; i < sigma; ++i) {
      buf[i] = buf[i - 1] + bucket[i];
    }
    for(int i = len - 1; i >= 0; --i) {
      if(sa[i] <= 0) continue;
      if(type[sa[i] - 1] != S) continue;
      sa[--buf[str[sa[i] - 1]]] = sa[i] - 1;
    }
    delete[] bucket;
    delete[] buf;
    return;
  }
  template<typename T>
  void sais(T str, int len, int sigma, int *LMS) {
    type_t *type = new type_t[len];
    type[len - 1] = S;
    for(int i = len - 2; i >= 0; --i) {
      type[i] = str[i] < str[i + 1] ? S : L;
      if(str[i] != str[i + 1]) continue;
      type[i] = type[i + 1];
    }

    int LMSSize = 0;
    for(int i = 0; i < len; ++i) {
      if(!isLMS(type, i)) continue;
      LMS[LMSSize++] = i;
    }

    inducedSort(str, len, sigma, type, LMS, LMSSize);
    int pre = -1;
    int cnt = 0;
    int *temp = new int[len];
    for(int i = 0; i < len; ++i) {
      if(!isLMS(type, sa[i])) continue;
      if(!sameLMS(str, type, pre, sa[i])) ++cnt;
      temp[sa[i]] = cnt - 1;
      pre = sa[i];
    }
    int *s1 = new int[LMSSize];
    LMSSize = 0;
    for(int i = 0; i < len; ++i) {
      if(!isLMS(type, i)) continue;
      s1[LMSSize++] = temp[i];
    }
    delete[] temp;

    int *nextLMS = new int[LMSSize];
    if(cnt < LMSSize) {
      sais(s1, LMSSize, cnt, nextLMS);
    } else {
      for(int i = 0; i < LMSSize; ++i) {
        sa[s1[i]] = i;
      }
    }
    delete[] s1;
    for(int i = 0; i < LMSSize; ++i) {
      nextLMS[i] = LMS[sa[i]];
    }

    inducedSort(str, len, sigma, type, nextLMS, LMSSize);
    delete[] nextLMS;
    delete[] type;
    return;
  }
 public:
  int sa[MAX_LEN];
  int rank[MAX_LEN];
  template<typename T>
  void init(T str, int len, int sigma) {
    int *LMS = new int[len];
    sais(str, len + 1, sigma, LMS);
    delete[] LMS;
    for(int i = 0; i < len; ++i) {
      sa[i] = sa[i + 1] + 1;
      rank[sa[i]] = i;
    }
  }
} sais;

char str[MAX_LEN];

int main() {
  scanf("%s", str);
  int len = strlen(str);
  sais.init(str, len, 128);
  for(int i = 0; i < len; ++i) {
    printf("%d ", sais.sa[i]);
  }
  return 0;
}

后来写的方便快速打出来的版本：

#include<cstdio>
#include<cstring>
#include<algorithm>
const int MAX_LEN = 1e6 + 5;
const int SIGMA = 128;
char s[MAX_LEN];
int str[MAX_LEN << 1];
int type[MAX_LEN << 1];
int LMS[MAX_LEN << 1];
int sa[MAX_LEN];
int rank[MAX_LEN];
int height[MAX_LEN];
int cnt[MAX_LEN];
int cur[MAX_LEN];
void inducedsort(int *str, int len, int sigma, int *LMS, int LMSC, int *type) {
    #define PUSH_S(x) (sa[cur[str[x]]--] = x)
    #define PUSH_L(x) (sa[cur[str[x]]++] = x)
    std::fill_n(sa, len, -1), std::fill_n(cnt, sigma, 0);
    for(int i = 0; i < len; ++i) ++cnt[str[i]];
    for(int i = 1; i < sigma; ++i) cnt[i] += cnt[i - 1];
    for(int i = 0; i < sigma; ++i) cur[i] = cnt[i] - 1;
    for(int i = LMSC - 1; i >= 0; --i) PUSH_S(LMS[i]);
    for(int i = 1; i < sigma; ++i) cur[i] = cnt[i - 1];
    for(int i = 0; i < len; ++i) sa[i] > 0 && type[sa[i] - 1] == 0 && PUSH_L(sa[i] - 1);
    for(int i = 0; i < sigma; ++i) cur[i] = cnt[i] - 1;
    for(int i = len - 1; i >= 0; --i) sa[i] > 0 && type[sa[i] - 1] && PUSH_S(sa[i] - 1);
    #undef PUSH_S
    #undef PUSH_L
}
void sais(int *str, int len, int sigma, int *LMS, int *type) {
    type[len - 1] = 1;
    for(int i = len - 2; i >= 0; --i) type[i] = (str[i] == str[i + 1] ? type[i + 1] : str[i] < str[i + 1]);
    int LMSC = 0;
    rank[0] = -1;
    for(int i = 1; i < len; ++i) rank[i] = (type[i] && !type[i - 1]) ? (LMS[LMSC] = i, LMSC++) : -1;
    inducedsort(str, len, sigma, LMS, LMSC, type);
    int tot = -1;
    int *s1 = str + len;
    for(int i = 0, now, last; i < len; ++i) if(-1 != (now = rank[sa[i]])) {
        if(tot < 1 || LMS[now + 1] - LMS[now] != LMS[last + 1] - LMS[last]) ++tot;
        else for(int j = LMS[now], k = LMS[last]; j < LMS[now + 1]; ++j, ++k) if((str[j] << 1 | type[j]) != (str[k] << 1 | type[k])) {
            ++tot;
            break;
        }
        s1[last = now] = tot;
    }
    if(tot + 1 < LMSC) sais(s1, LMSC, tot + 1, LMS + LMSC, type + len);
    else for(int i = 0; i < LMSC; ++i) sa[s1[i]] = i;
    for(int i = 0; i < LMSC; ++i) s1[i] = LMS[sa[i]];
    inducedsort(str, len, sigma, s1, LMSC, type);
}
void SA() {
    int len = strlen(s);
    for(int i = 0; i < len; ++i) str[i] = s[i];
    sais(str, len + 1, SIGMA, LMS, type);
    for(int i = 0; i <= len; ++i) rank[sa[i]] = i;
    for(int i = 0, k = 0; i <= len; height[rank[i++]] = k) {
        k && --k;
        if(rank[i] != 0) while(str[i + k] == str[sa[rank[i] - 1] + k]) ++k;
    }
    return;
}
int main() {
    scanf("%s", s);
    SA();
    return 0;
}