代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

#define REP(i, a, b) for(int i = (a); i <= (b); ++ i)
#define PER(i, a, b) for(int i = (a); i >= (b); -- i)

int n;
char s[N];

namespace SA {
  int Mem[N * 10], sa[N], H[N], rk[N];
  
  void build(int m) {
    int *x = Mem, *y = Mem + (N << 1), *z = y + (N << 1);
    REP(i, 1, m) z[i] = 0;
    REP(i, 1, n) ++ z[x[i] = s[i]];
    REP(i, 1, m) z[i] += z[i - 1];
    REP(i, 1, n) sa[z[x[i]] --] = i;
    for(int k = 1; k <= n; k <<= 1) {
      int p = 0;
      REP(i, n - k + 1, n) y[++ p] = i;
      REP(i, 1, n) if(sa[i] > k) y[++ p] = sa[i] - k;
      REP(i, 1, m) z[i] = 0;
      REP(i, 1, n) ++ z[x[i]];
      REP(i, 1, m) z[i] += z[i - 1];
      PER(i, n, 1) sa[z[x[y[i]]] --] = y[i];
      swap(x, y); p = 0;
      REP(i, 1, n) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++ p;
      if(p == n) break;
      m = p;
    }
  }

  void getheight() {
    int Now = 0;
    REP(i, 1, n) rk[sa[i]] = i;
    REP(i, 1, n) {
      if(Now) -- Now;
      if(rk[i] == n) continue;
      while(s[i + Now] == s[sa[rk[i] + 1] + Now]) ++ Now;
      H[rk[i]] = Now;
    }
  }
}

int main() {
  scanf("%s", s + 1); n = strlen(s + 1);
  SA :: build('z');
  SA :: getheight();
  REP(i, 1, n) printf("%d ", SA :: sa[i]); puts("");
  REP(i, 1, n - 1) printf("%d ", SA :: H[i]); puts("");
}

评测结果