代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define reo(i,j,k) for(int i=j;i>=k;i--)
#define mem memset
#define mpy memcpy
typedef long long ll;
constexpr int N = 1e6 + 10;
int n, m = 26, p, sa[N], rk[N], se[N], cnt[N], ht[N];
char s[N];
inline void rsort() {
    rep(i, 1, m) cnt[i] = 0;
    rep(i, 1, n) cnt[rk[i]]++;
    rep(i, 1, m) cnt[i] += cnt[i - 1];
    reo(i, n, 1) sa[cnt[rk[se[i]]]--] = se[i];
}
inline void SA() {
	if (n == 1) return (void)(rk[1] = 1, sa[1] = 1);
    rep(i, 1, n) rk[i] = s[i] - 'a' + 1, se[i] = i; rsort();
    for (int w = 1; w < n; w <<= 1, m = p) {
        p = 0;
        rep(i, n - w + 1, n) se[++p] = i;
        rep(i, 1, n) if (sa[i] > w) se[++p] = sa[i] - w;
        rsort(), swap(rk, se);
        p = 0;
        rep(i, 1, n) 
            if (se[sa[i]] == se[sa[i - 1]] && se[sa[i] + w] == se[sa[i - 1] + w]) rk[sa[i]] = p;
            else rk[sa[i]] = ++p;
        if (p == n) return;
    }
}
int main() {
    scanf("%s", s + 1), n = strlen(s + 1), SA();
    rep(i, 1, n) printf("%d%c", sa[i], " \n"[i == n]);
	for (int i = 1, k = 0; i <= n; i++) {
		if (k) k--;
		while (s[i + k] == s[sa[rk[i] - 1] + k]) k++;
		ht[rk[i]] = k;
	}
	rep(i, 2, n) printf("%d ", ht[i]);
	puts("");
}

评测结果