Suffix array - YessineJallouli/Competitive-Programming GitHub Wiki
void suffix_array(string &s) {
s+= '$';
/// Let's use three vectors :
/// a contains as left part the pair of two equivalence classes and as the second part the index
/// p contains the ordering of the strings
/// c contains the equivalence classes
int n = s.size();
vector<int> p(n), c(n);
{
vector<pair<char,int>> a(n);
for (int i = 0; i < n; i++) {
a[i] = {s[i], i};
}
sort(a.begin(), a.end());
for (int i = 0; i < n; i++)
p[i] = a[i].second;
c[p[0]] = 0;
for (int i = 1; i < n; i++) {
c[p[i]] = c[p[i-1]];
if (a[i].first != a[i-1].first)
c[p[i]]++;
}
}
int k = 0;
while ((1 << k) < n) {
vector<pair<pair<int,int>, int>> a(n);
for (int i = 0; i < n; i++) {
a[i] = {{c[i], c[(i+(1<<k))%n]}, i};
}
sort(a.begin(), a.end());
for (int i = 0; i < n; i++)
p[i] = a[i].second;
c[p[0]] = 0;
for (int i = 1; i < n; i++) {
c[p[i]] = c[p[i-1]];
if (a[i].first != a[i-1].first)
c[p[i]]++;
}
k++;
}
for (int i : p)
cout << i << ' ';
}
Optimizations :
void count_sort(vector<int> &p, vector<int> &c) {
int n = p.size();
vector<int> cnt(n);
for (auto x : c) {
cnt[x]++;
}
vector<int> new_p(n);
vector<int> pos(n);
pos[0] = 0;
for (int i = 1; i < n; i++) {
pos[i] = pos[i-1] + cnt[i-1];
}
for (auto x : p) {
int i = c[x];
new_p[pos[i]] = x;
pos[i]++;
}
p = new_p;
}
void suffix_array(string &s) {
s+= '$';
int n = s.size();
vector<int> p(n), c(n);
{
vector<pair<char,int>> a(n);
for (int i = 0; i < n; i++) {
a[i] = {s[i], i};
}
sort(a.begin(), a.end());
for (int i = 0; i < n; i++)
p[i] = a[i].second;
c[p[0]] = 0;
for (int i = 1; i < n; i++) {
c[p[i]] = c[p[i-1]];
if (a[i].first != a[i-1].first)
c[p[i]]++;
}
}
int k = 0;
while ((1 << k) < n) {
for (int i = 0; i < n; i++)
p[i] = (p[i] - (1 << k) + n) % n;
count_sort(p,c);
vector<int> new_c(n);
new_c[p[0]] = 0;
for (int i = 1; i < n; i++) {
new_c[p[i]] = new_c[p[i-1]];
pair<int,int> p1 = {c[p[i]], c[(p[i]+(1<<k))%n]};
pair<int,int> p2 = {c[p[i-1]], c[(p[i-1]+(1<<k))%n]};
if (p1 != p2)
new_c[p[i]]++;
}
c = new_c;
k++;
}
for (int i : p)
cout << i << ' ';
}
Resources : https://codeforces.com/edu/course/2/lesson/2