suffix array

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

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T = 1;
     //~ cin >> T;
     for (int t = 1; t <= T; ++t) {
        string s;
        cin >> s;
        s += '$';
        int n = s.size();
        int order[n]; // order
        int class_[n]; // equivalent class
        pair<char,int> pos[n]; // position
        for (int i = 0; i < n; ++i) {
            pos[i] = make_pair(s[i],i);
        }
        sort(pos, pos + n);
        for (int i = 0; i < n; ++i) {
            order[i] = pos[i].second;
        }
        class_[order[0]] = 0;
        for (int i = 1; i < n; ++i) {
            if (pos[i].first == pos[i - 1].first) {
                class_[order[i]] = class_[order[i - 1]];
            } else {
                class_[order[i]] = class_[order[i - 1]] + 1;
            }
        }
        int k = 0;
        while ((1 << k) < n) {
            pair<pair<int,int>,int> suf[n]; //positon array
            for (int i = 0; i < n; ++i) {
                suf[i] = make_pair(make_pair(class_[i],class_[(i + (1 << k)) % n]),i);
            }
            sort(suf,suf + n);
            for (int i = 0; i < n; ++i) {
                order[i] = suf[i].second;
            }
            class_[order[0]] = 0; // first class to be order[0] = 0
            for (int i = 1; i < n; ++i) {
                if (suf[i].first == suf[i - 1].first) {
                    class_[order[i]] = class_[order[i - 1]];
                } else {
                    class_[order[i]] = class_[order[i - 1]] + 1;
                }
            }
            k += 1;
        }
        for (int i = 0; i < n; ++i) {
            cout << order[i] << " ";
        }
     }
}