vector<int> suffix_array(const string& in) {
int n = (int)in.size(), c = 0;
vector<int> temp(n), pos2bckt(n), bckt(n), bpos(n), out(n);
for (int i = 0; i < n; i++) out[i] = i;
sort(out.begin(), out.end(), [&](int a, int b) { return in[a] < in[b]; });
for (int i = 0; i < n; i++) {
bckt[i] = c;
if (i + 1 == n || in[out[i]] != in[out[i + 1]]) c++;
}
/*Start*/
for (int h = 1; h < n && c < n; h <<= 1) {// executes log n times
for (int i = 0; i < n; i++) pos2bckt[out[i]] = bckt[i];
for (int i = n - 1; i >= 0; i--) bpos[bckt[i]] = i;
for (int i = 0; i < n; i++)
if (out[i] >= n - h) temp[bpos[bckt[i]]++] = out[i];
for (int i = 0; i < n; i++)
if (out[i] >= h) temp[bpos[pos2bckt[out[i] - h]]++] = out[i] - h;
c = 0;
for (int i = 0; i + 1 < n; i++) {
int a = (bckt[i] != bckt[i + 1]) || (temp[i] >= n - h)
|| (pos2bckt[temp[i + 1] + h] != pos2bckt[temp[i] + h]);
bckt[i] = c;
c += a;
}
bckt[n - 1] = c++;
temp.swap(out);
}
return out;
}