Test/yosupo-Suffix-Array.test.cpp

• View this file on GitHub
• Last update: 2023-07-19 13:59:31+00:00
• Problem: https://judge.yosupo.jp/problem/suffixarray

Depends on

• SuffixArray (String/SuffixArray.hpp)

Code

#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://judge.yosupo.jp/problem/suffixarray"

#include "../String/SuffixArray.hpp"

int main() {

    string S; cin >> S;
    vector<int> sa = SuffixArray(S);
    for (int i = 1; i < sa.size(); i++) {
        cout << sa[i] << " \n"[i == sa.size() - 1];
    }

}

#line 1 "Test/yosupo-Suffix-Array.test.cpp"
#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://judge.yosupo.jp/problem/suffixarray"

#line 1 "String/SuffixArray.hpp"
vector<int> SuffixArray(const string& s) {
    int n = s.size(), k;
    vector<int> sa(n + 1);
    vector<int> rank(n + 1);
    for (int i = 0; i <= n; i++) {
        sa[i] = i;
        rank[i] = i < n ? (int)s[i] : -1;
    }

    auto compare = [&](int a, int b) {
        if (rank[a] != rank[b]) return rank[a] < rank[b];
        auto rank_ak = a + k <= n ? rank[a + k] : -1;
        auto rank_bk = b + k <= n ? rank[b + k] : -1;
        return rank_ak < rank_bk;
    };

    for (k = 1; k <= n; k *= 2) {
        sort(sa.begin(), sa.end(), compare);
        vector<int> tmp(n + 1);
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (compare(sa[i - 1], sa[i]) ? 1 : 0);
        }
        for (int i = 0; i <= n; i++) {
            rank[i] = tmp[i];
        }
    }
    return sa;
}
#line 7 "Test/yosupo-Suffix-Array.test.cpp"

int main() {

    string S; cin >> S;
    vector<int> sa = SuffixArray(S);
    for (int i = 1; i < sa.size(); i++) {
        cout << sa[i] << " \n"[i == sa.size() - 1];
    }

}

Back to top page