string/suffix_array.hpp

• View this file on GitHub
• Last update: 2024-12-01 17:46:49+09:00
• Include: #include "string/suffix_array.hpp"

Verified with

• verify/yosupo/yosupo_longest_common_substring.test.cpp
• verify/yosupo/yosupo_suffix_array.test.cpp

Code

vector<int> suffix_array(const string& S) {
    int N = S.size();
    vector<int> rank(N), sa(N);

    for(int i = 0; i < N; i++) {
        sa[i] = i;
        rank[i] = S[i];
    }

    for(int k = 1; k < N; k *= 2) {
        auto get_rank = [&](int i) -> int { return (i < N) ? rank[i] : 0; };

        auto radix_sort = [&](int k) -> void {
            const int CHAR_SIZE = 130;
            vector<int> backet(max(N + 1, CHAR_SIZE), 0), nsa(N);
            for(int i = 0; i < N; i++) {
                backet[get_rank(i + k)]++;
            }
            for(int i = 1; i < backet.size(); i++) {
                backet[i] += backet[i - 1];
            }
            for(int i = N; i--;) {
                int& x = backet[get_rank(sa[i] + k)];
                nsa[--x] = sa[i];
            }
            swap(sa, nsa);
        };
        radix_sort(k);
        radix_sort(0);

        vector<int> nrank(N);
        nrank[sa[0]] = 1;
        for(int i = 1; i < N; i++) {
            bool is_different = (get_rank(sa[i - 1]) != get_rank(sa[i]) || get_rank(sa[i - 1] + k) != get_rank(sa[i] + k));
            nrank[sa[i]] = nrank[sa[i - 1]] + is_different;
        }
        swap(rank, nrank);
    }

    return sa;
}

#line 1 "string/suffix_array.hpp"
vector<int> suffix_array(const string& S) {
    int N = S.size();
    vector<int> rank(N), sa(N);

    for(int i = 0; i < N; i++) {
        sa[i] = i;
        rank[i] = S[i];
    }

    for(int k = 1; k < N; k *= 2) {
        auto get_rank = [&](int i) -> int { return (i < N) ? rank[i] : 0; };

        auto radix_sort = [&](int k) -> void {
            const int CHAR_SIZE = 130;
            vector<int> backet(max(N + 1, CHAR_SIZE), 0), nsa(N);
            for(int i = 0; i < N; i++) {
                backet[get_rank(i + k)]++;
            }
            for(int i = 1; i < backet.size(); i++) {
                backet[i] += backet[i - 1];
            }
            for(int i = N; i--;) {
                int& x = backet[get_rank(sa[i] + k)];
                nsa[--x] = sa[i];
            }
            swap(sa, nsa);
        };
        radix_sort(k);
        radix_sort(0);

        vector<int> nrank(N);
        nrank[sa[0]] = 1;
        for(int i = 1; i < N; i++) {
            bool is_different = (get_rank(sa[i - 1]) != get_rank(sa[i]) || get_rank(sa[i - 1] + k) != get_rank(sa[i] + k));
            nrank[sa[i]] = nrank[sa[i - 1]] + is_different;
        }
        swap(rank, nrank);
    }

    return sa;
}

Back to top page