-
Notifications
You must be signed in to change notification settings - Fork 11
/
kattis_burrowswheeler.cpp
110 lines (102 loc) · 4.04 KB
/
kattis_burrowswheeler.cpp
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
/**Kattis - burrowswheeler
* We can reduce this problem to a suffix array construction problem using the heuristic of
* letting T = T + T[:-1]. Now, the first n characters of the first n suffixes form the cyclical
* permutations of our original T. Instead of worrying about how to extact only the first n
* suffixes, we just construct a SA as usual and only consider a suffix if it is < n. If so,
* we get the nth character with T[i+n-1] where i is the first index of the suffix.
*
* Time: O(n log n), Space: O(n)
*/
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
class SuffixArray {
private:
vi RA; // rank array
void countingSort(int k) { // O(n)
int maxi = max(300, n); // up to 255 ASCII chars
vi c(maxi, 0); // clear frequency table
for (int i = 0; i < n; ++i) // count the frequency
++c[i + k < n ? RA[i + k] : 0]; // of each integer rank
for (int i = 0, sum = 0; i < maxi; ++i) {
int t = c[i];
c[i] = sum;
sum += t;
}
vi tempSA(n);
for (int i = 0; i < n; ++i) // sort SA
tempSA[c[SA[i] + k < n ? RA[SA[i] + k] : 0]++] = SA[i];
swap(SA, tempSA); // update SA
}
void constructSA() { // can go up to 400K chars
SA.resize(n);
iota(SA.begin(), SA.end(), 0); // the initial SA
RA.resize(n);
for (int i = 0; i < n; ++i) RA[i] = T[i]; // initial rankings
for (int k = 1; k < n; k <<= 1) { // repeat log_2 n times
// this is actually radix sort
countingSort(k); // sort by 2nd item
countingSort(0); // stable-sort by 1st item
vi tempRA(n);
int r = 0;
tempRA[SA[0]] = r; // re-ranking process
for (int i = 1; i < n; ++i) // compare adj suffixes
tempRA[SA[i]] = // same pair => same rank r; otherwise, increase r
((RA[SA[i]] == RA[SA[i - 1]]) && (RA[SA[i] + k] == RA[SA[i - 1] + k])) ? r
: ++r;
swap(RA, tempRA); // update RA
if (RA[SA[n - 1]] == n - 1) break; // nice optimization
}
}
void computeLCP() {
vi Phi(n);
vi PLCP(n);
PLCP.resize(n);
Phi[SA[0]] = -1; // default value
for (int i = 1; i < n; ++i) // compute Phi in O(n)
Phi[SA[i]] = SA[i - 1]; // remember prev suffix
for (int i = 0, L = 0; i < n; ++i) { // compute PLCP in O(n)
if (Phi[i] == -1) {
PLCP[i] = 0;
continue;
} // special case
while ((i + L < n) && (Phi[i] + L < n) && (T[i + L] == T[Phi[i] + L]))
++L; // L incr max n times
PLCP[i] = L;
L = max(L - 1, 0); // L dec max n times
}
LCP.resize(n);
for (int i = 0; i < n; ++i) // compute LCP in O(n)
LCP[i] = PLCP[SA[i]]; // restore PLCP
}
public:
string T; // the initial string
const int n; // the length of T
vi SA; // Suffix Array
vi LCP; // of adj sorted suffixes
SuffixArray(string initialT) : T(initialT), n(initialT.size()) {
constructSA(); // O(n log n)
computeLCP(); // O(n)
}
};
string T;
int main() {
while (getline(cin, T)) {
int n = T.size();
T += T;
T.pop_back(); // remove the last character to prevent the original string from being
// included twice
T += char(9); // add terminal char
SuffixArray SA(T);
for (auto i : SA.SA) {
if (i >= n) continue;
cout << T[i + n - 1];
}
cout << endl;
}
return 0;
}