Добрый день, мой вклад упал я давно не писал ничего полезного, поэтому надо что-то написать.
0) Постановка задачи и реализация. Хотим лексикографически отсортировать все суффиксы (или циклические сдвиги) строки s по возрастанию. Суффиксный массив — это такая перестановка p чисел от 0 до n — 1, что p[i] — обозначает позицию начала лексикографически i-того суффикса строки, то есть это то, что позволит решить нашу задачу.
Для построения суффиксного массива мы будем использовать классы эквивалентности — c[i][len], которое обозначает, что циклический сдвиг, начиная с i-той позиции длины len имеет класс эквивалентности $$$c[i][len]$$$. При чем для двух классов эквивалентности $$$c[i][len]$$$ и $$$c[j][len]$$$ будет верно, что $$$c[i][len] == c[j][len]$$$ тогда и только тогда, когда соответствующие подстроки равны, а $$$c[i][len] < c[j][len]$$$ тогда и только тогда, когда i-тая подстрока лексикографически меньше j-той. Таким образом, если мы расставим классы для длины $$$len >= len(s)$$$, то мы очень просто сможем восстановить перестановку p.
Пусть мы расставили классы для длины len. Расставим для длины 2 * len. Но заметим, что класс c[i][2 * len] описывается парой $$$\{c[i][len], c[i + len][len]\}$$$, то есть какой результат сравнения будет у двух таких пар, такой будет и у соответствующих суффиксов. Поэтому мы можем отсортировать все пары и расставить новые классы для длины 2 * len, а сложность будет $$$O(\log n * n \log n) = O(n \log^2 n)$$$, так как мы будем увеличивать длину как степень двойки ($$$\log n$$$), а на каждой итерации мы будем сортировать n пар обычной сортировкой ($$$n \log n$$$).

Многие (в том числе и я) не любят суфмасс из-за его громоздкости и не очень понятной реализации, в которой легко набагать. На e-maxx, например, он занимает 50 строк и строки вида $$$p[--cnt[c[pn[i]]]] = pn[i];$$$ не очень крутые.

1) Моя реализация за $$$O(n \log^2 n)$$$:

vector<int> sufmas(vector<int> c) {
	int n = c.size();
	vector<pair<pair<int, int>, int>> t(n); //t[i] = { { first class, second class }, position }
	for (int i = 1; i < n; i <<= 1) {
		for (int j = 0; j < c.size(); j++)
			t[j] = { { c[j], c[(j + i) % n] }, j };
		sort(t.begin(), t.end());
		for (int cnt = 0, j = 0; j < n; j++) {
			if (j && t[j].first != t[j - 1].first)
				cnt++;
			c[t[j].second] = cnt;
		}
	} 

	vector<int> p(n);
	for (int i = 0; i < n; i++)
		p[c[i]] = i;
	return p;
}

2) Чтобы убрать лишний логарифм в сложности, можно воспользоваться цифровой сортировкой, которая лучше использует то, что на предыдущем шаге мы уже отсортировали суффиксы меньшей длины.
Тут задумывалась моя короткая реализация суффиксного массива за $$$O(n \log n)$$$, однако на практике мы выяснили, что она работает дольше первой, поэтому я оставлю здесь ссылку на короткую реализацию от Пядеркина за аналогичную асимптотику.
Также хочу сказать спасибо за помощь в написании этого поста Holidin, ismagilov.code и SpeedOfMagic