-
Notifications
You must be signed in to change notification settings - Fork 0
/
suffix_array.cpp
101 lines (101 loc) · 3.4 KB
/
suffix_array.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
// Manber-Myers Algorithm for Suffix Array
// Time Conplexity: O(nlog^2n)
// Kasai's Algorithm for LCP(Longest Common Prefix)
// Time Complexity: O(n)
// BOJ 9248 AC Code
// https://www.acmicpc.net/problem/9248
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()
vector<int> buildsa(const string& s) {
int n = sz(s);
vector<int> sa(n), r(n + 1), nr(n + 1);
for (int i = 0; i < n; i++) sa[i] = i, r[i] = s[i];
for (int d = 1; d < n; d <<= 1) {
auto cmp = [&](int i, int j) {
if (r[i] ^ r[j]) return r[i] < r[j];
return r[i + d] < r[j + d];
};
sort(sa.begin(), sa.end(), cmp);
nr[sa[0]] = 1;
for (int i = 1; i < n; i++)
nr[sa[i]] = nr[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
r = nr;
}
return sa;
}
vector<int> buildlcp(const string& s, const vector<int>& sa) {
int n = sz(s);
vector<int> lcp(n), isa(n);
for (int i = 0; i < n; i++) isa[sa[i]] = i;
for (int k = 0, i = 0; i < n; i++) if (isa[i]) {
for (int j = sa[isa[i] - 1]; s[i + k] == s[j + k]; k++);
lcp[isa[i]] = (k ? k-- : 0);
}
return lcp;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios_base::sync_with_stdio(false);
string s; cin >> s;
vector<int> sa = buildsa(s);
vector<int> lcp = buildlcp(s, sa);
for (auto& i : sa) cout << i + 1 << ' ';
cout << '\n';
cout << "x ";
for (int i = 1; i < sz(lcp); i++) cout << lcp[i] << ' ';
}
// Manber-Myers Algorithm for Suffix Array
// Time Conplexity: O(nlogn)
// Kasai's Algorithm for LCP(Longest Common Prefix)
// Time Complexity: O(n)
// BOJ 9248 AC Code
// https://www.acmicpc.net/problem/9248
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()
vector<int> buildsa(const string& s) {
int n = sz(s), m = max(256, n) + 1;
vector<int> sa(n), r(2 * n), nr(2 * n), cnt(m), idx(n);
for (int i = 0; i < n; i++) sa[i] = i, r[i] = s[i];
for (int d = 1; d < n; d <<= 1) {
auto cmp = [&](int i, int j) {
if (r[i] ^ r[j]) return r[i] < r[j];
return r[i + d] < r[j + d];
};
for (int i = 0; i < m; i++) cnt[i] = 0;
for (int i = 0; i < n; i++) cnt[r[i + d]]++;
for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for (int i = n - 1; ~i; i--) idx[--cnt[r[i + d]]] = i;
for (int i = 0; i < m; i++) cnt[i] = 0;
for (int i = 0; i < n; i++) cnt[r[i]]++;
for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for (int i = n - 1; ~i; i--) sa[--cnt[r[idx[i]]]] = idx[i];
nr[sa[0]] = 1;
for (int i = 1; i < n; i++) nr[sa[i]] = nr[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
for (int i = 0; i < n; i++) r[i] = nr[i];
if (r[sa[n - 1]] == n) break;
}
return sa;
}
vector<int> buildlcp(const string& s, const vector<int>& sa) {
int n = sz(s);
vector<int> lcp(n), isa(n);
for (int i = 0; i < n; i++) isa[sa[i]] = i;
for (int k = 0, i = 0; i < n; i++) if (isa[i]) {
for (int j = sa[isa[i] - 1]; s[i + k] == s[j + k]; k++);
lcp[isa[i]] = (k ? k-- : 0);
}
return lcp;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios_base::sync_with_stdio(false);
string s; cin >> s;
vector<int> sa = buildsa(s);
vector<int> lcp = buildlcp(s, sa);
for (auto& i : sa) cout << i + 1 << ' ';
cout << '\n';
cout << "x ";
for (int i = 1; i < sz(lcp); i++) cout << lcp[i] << ' ';
}