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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::swap;
static bool debug = false;
class Bwt
{
private:
vector<int> v;
const string &s;
int sz;
void print(int n)
{
cout << "print : " << n << endl;
for (int i = 0; i < v.size(); i++)
cout << v[i] << ";" << s[(v[i] + n) % sz] << endl;
}
void print()
{
cout << "print : " << endl;
for (int i = 0; i < v.size(); i++) {
for (int j = 0; j < sz; j++)
cout << s[(v[i] + j) % sz];
cout << endl;
}
}
public:
Bwt(const string& text) : s(text), sz(text.size()) {
v.reserve(s.size());
for (int i = 0; i < s.size(); i++)
v.push_back(i);
if (debug) print();
}
string solve() {
sort(0, 0, v.size() - 1);
if (debug) print();
string ret = "";
for (int i = 0; i < v.size(); i++)
ret += s[(v[i] + sz - 1) % sz];
return ret;
}
private:
void sort(int x, int l, int r)
{
if (debug) cout << " sort: " << x << ";" << l << ";" << r << endl;
if (l >= r)
return;
quicksort(x, l, r);
if (debug) print();
char c = s[(v[l] + x) % sz];
int ll = l;
for (int i = l + 1; i <= r; i++) {
char C = s[(v[i] + x) % sz];
if (C != c) {
sort(x + 1, ll, i - 1);
ll = i;
c = C;
}
}
sort(x + 1, ll, r);
}
void quicksort(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) % sz];
int i = l + 1;
int j = r;
int k = r;
while (i <= j) {
int C = s[(v[j] + x ) % sz];
if (C < c) {
swap(v[i], v[j]);
i++;
} else if (C > c) {
swap(v[j], v[k]);
k--;
j--;
}
else
j--;
}
quicksort(x, l, i - 1);
quicksort(x, k + 1, r);
}
};
int main() {
string text;
cin >> text;
cout << Bwt(text).solve() << endl;
return 0;
}
|
