1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
using std::string;
using std::vector;
using std::swap;
static void quicksort(const string &s, vector<int> &v, int x, int l, int r)
{
if (l >= r)
return;
int p = l + rand() % (r - l + 1);
swap(v[l], v[p]);
char c = s[v[l] + x];
int i = l + 1;
int j = r;
int k = r;
while (i <= j) {
int C = s[v[j] + x];
if (C < c) {
swap(v[i], v[j]);
i++;
} else if (C > c) {
swap(v[j], v[k]);
k--;
j--;
}
else
j--;
}
quicksort(s, v, x, l, i - 1);
quicksort(s, v, x, k + 1, r);
}
static void sort(const string &s, vector<int> &v, int x, int l, int r)
{
if (l >= r)
return;
quicksort(s, v, x, l, r);
char c = s[v[l] + x];
int ll = l;
for (int i = l + 1; i <= r; i++) {
char C = s[v[i] + x];
if (C != c) {
sort(s, v, x + 1, ll, i - 1);
ll = i;
c = C;
}
}
sort(s, v, x + 1, ll, r);
}
// Build suffix array of the string text and
// return a vector result of the same length as the text
// such that the value result[i] is the index (0-based)
// in text where the i-th lexicographically smallest
// suffix of text starts.
vector<int> BuildSuffixArray(const string& text)
{
int sz = text.size();
vector<int> v;
v.reserve(text.size());
for (int i = 0; i < sz; i++)
v.push_back(i);
sort(text, v, 0, 0, sz - 1);
return v;
}
int main() {
string text;
cin >> text;
vector<int> suffix_array = BuildSuffixArray(text);
for (int i = 0; i < suffix_array.size(); ++i) {
cout << suffix_array[i] << ' ';
}
cout << endl;
return 0;
}
|
