代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e6 + 50;

int n, m;
int x[maxn], y[maxn], sa[maxn];
int c[maxn];

char s[maxn];


void SORT() {
	for (int i = 0; i <= m; i++) c[i] = 0;
	for (int i = 1; i <= n; i++) c[x[i]]++;
	for (int i = 1; i <= m; i++) c[i] = c[i - 1] + c[i];
	for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];
}

void SA() {
	m = 123;
	for (int i = 1; i <= n; i++) x[i] = s[i] - '0' + 1, y[i] = i;
	SORT();
	for (int k = 1; k <= n; k <<= 1){
		int p = 0;
		for (int i = n - k +1; i  <= n; i++) y[++p] = i;
		for (int i = 1; i <= n; i++) if (sa[i] > k) y[++p] = sa[i] - k;
		SORT();
		swap(x, y);
		x[sa[1]] = p = 1;
		for (int i = 2; i <= n; i++) 
			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++p;
		m = p;
		if (m == n) break;
	}
}
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	SA();
	for (int i = 1; i <= n; i++) printf("%d ", sa[i]);
}

评测结果