https://www.luogu.com.cn/problem/P3809
#include <bits/stdc++.h>
using namespace std;
int sa[1000005], sb[1000005];
char str[1000005];
int a[1000005];
int n;
int get(int l, int r) {
return sb[r] - sb[l - 1] * sa[r - l + 1];
}
bool cmp(int l1, int l2) {
int l = -1, r = min(n - l1, n - l2);
while (l < r) {
int mid = (l + r + 1) >> 1;
if (get(l1, l1 + mid) == get(l2, l2 + mid)) l = mid;
else r = mid - 1;
}
if (l > min(n - l1, n - l2)) return l1 > l2;
else return str[l1 + l + 1] < str[l2 + l + 1];
}
int main(void)
{
cin >> (str + 1);
n = strlen(str + 1);
sa[0] = 1;
for (int i = 1; i <= n; i++) {
sa[i] = sa[i - 1] - 'a';
sb[i] = sb[i - 1] - 'a' + str[i];
a[i] = i;
}
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++) {
cout << a[i] << ' ';
}
return 0;
}