```cpp
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1000000 + 5;
class SuffixArray
{
private:
int *t, *t2, *c;
int *sa;
private:
bool cmp(int *r, int a, int b, int l) {
return (r[a] == r[b]) && (r[a + l] == r[b + l]);
}
int expchar(char a) {
if(a >= '0' && a <= '9') return a - '0';
if(a >= 'A' && a <= 'Z') return a - 'A' + 10;
if(a >= 'a' && a <= 'z') return a - 'a' + 36;
throw "Wrong Char!";
}
void build(char *s, int n, int m)
{
int i, *x = t, *y = t2;
for(i = 0; i < m; ++i) c[i] = 0;
for(i = 0; i < n; ++i) ++c[x[i] = expchar(s[i])];
for(i = 1; i < m; ++i) c[i] += c[i - 1];
for(i = n - 1; i >= 0; --i) sa[--c[x[i]]] = i;
for(int k = 1; k <= n; k <<= 1)
{
int p = 0;
for(i = n - k; i < n; ++i) y[p++] = i;
for(i = 0; i < n; ++i) if(sa[i] >= k) y[p++] = sa[i] - k;
for(i = 0; i < m; ++i) c[i] = 0;
for(i = 0; i < n; ++i) ++c[x[y[i]]];
for(i = 1; i < m; ++i) c[i] += c[i - 1];
for(i = n - 1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = 1; x[sa[0]] = 0;
for(i = 1; i < n; ++i)
x[sa[i]] = cmp(y, sa[i - 1], sa[i], k)? p - 1: p++;
if(p >= n) break;
m = p;
}
}
public:
SuffixArray(char *s, int n, int m) {
t = new int[n];
t2 = new int[n];
c = new int[m];
sa = new int[n];
build(s, n, m);
delete[] t;
delete[] t2;
delete[] c;
}
~SuffixArray() {
delete[] sa;
}
public:
int operator [] (int num) const {
return sa[num];
}
};
int main()
{
char s[maxn];
int n;
cin >> s;
n = strlen(s);
SuffixArray sa = SuffixArray(s, n, 62);
for(int i = 0; i < n; ++i) cout << sa[i] + 1 << ' ';
cout << endl;
return 0;
}
```
by cjrsacred @ 2017-12-03 19:08:33