competitive-programming/suffix_array.cpp at main · dryeab/competitive-programming · GitHub

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
#include <bits/stdc++.h>

using namespace std;

int main() {

    string s;
    cin >> s;

    s += "$";

    int n = s.size();
    vector<int> p(n), c(n);

    {
        vector<pair<int, 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;

        // p[i] : index of the suffix which is ith when sorted
        // c[i] : rank of suffix S[i: ...]

        c[p[0]] = 0;

        for (int i = 1; i < n; ++i) {
            if (a[i].first == a[i - 1].first)
                c[p[i]] = c[p[i - 1]];
            else
                c[p[i]] = c[p[i - 1]] + 1;
        }
    }

    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) {
            if (a[i].first == a[i - 1].first)
                c[p[i]] = c[p[i - 1]];
            else
                c[p[i]] = c[p[i - 1]] + 1;
        }

        k++;
    }

    for (int i = 0; i < n; ++i) {
        cout << p[i] << " ";
    }
}