Suffix array

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define long ll
#define all(x) begin(x), end(x)



int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    s += '#';
    int n = (int)s.size();
    s += s;

    vector<int> array;      /// Position -> suffix.
    vector<int> new_e(n);   /// New equiv.
    vector<int> equiv(n);   /// Classes of equivalence.
    static const int MAX_N = 1e5 + 5;
    static vector<int> bucket[MAX_N];


    for (int i = 0; i < n; ++i) {
        equiv[i] = s[i];
        bucket[equiv[i]].push_back(i);
    }
    array.clear();
    for (int i = 0; i < 256; ++i) {
        for (int suf : bucket[i]) {
            array.push_back(suf);
        }
        bucket[i].clear();
    }

    for (int l = 1; l < n; l *= 2) {
        int max_class = 0;
        for (int ind = 0; ind < n; ++ind) {
            int suf = (array[ind] + n - l) % n;
            // Test resize vs clear.
            // Test mem allocators.
            // Global.
            // int fir = array[ind] - l + n * (array[ind] < l);
            // int fir = array[ind] < l ? array[ind] + n - l : array[ind] - l;
            max_class = max(max_class, equiv[suf]);
            bucket[equiv[suf]].push_back(suf);
        }
        array.clear();
        for (int i = 0; i <= max_class; ++i) {
            for (int suf : bucket[i]) {
                array.push_back(suf);
            }
            bucket[i].clear();
        }
        new_e[array[0]] = 0;
        for (int i = 1; i < n; ++i) {
            int x = array[i], y = array[i - 1];
            new_e[x] = new_e[y];
            assert(equiv[x] >= equiv[y]);
            if (equiv[x] > equiv[y] || equiv[(x + l) % n] > equiv[(y + l) % n]) {
                ++new_e[x];
            }
        }
        equiv = new_e;
    }

    for (int i = 1; i < n; ++i) {
        cout << array[i] << '\n';
    }
    return 0;
}