string/suffix_array.cpp

• View this file on GitHub
• Last update: 2022-08-27 12:40:11+09:00

Code

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

vector<int> suffix_array(string &s) {
    // O(Nlog^2N)
    int n = s.size();
    vector<int> sa(n + 1), rank(n + 1), tmp(n + 1);
    for (int i = 0; i <= n; ++i) {
        sa[i]   = i;
        rank[i] = (i < n ? s[i] : -1);
    }
    for (int k = 1; k <= n; k <<= 1) {
        auto cmp = [&](int i, int j) {
            if (rank[i] != rank[j])
                return rank[i] < rank[j];
            else {
                int ri = (i + k <= n ? rank[i + k] : -1);
                int rj = (j + k <= n ? rank[j + k] : -1);
                return ri < rj;
            }
        };
        sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; ++i) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
        }
        for (int i = 0; i <= n; ++i) {
            rank[i] = tmp[i];
        }
    }
    return sa;
}

vector<int> lcp_array(string &s, vector<int> &sa) {
    int n = s.size();
    vector<int> rank(n);
    for (int i = 0; i < n; ++i) {
        rank[sa[i]] = i;
    }
}

#line 2 "string/suffix_array.cpp"
#include <bits/stdc++.h>
using namespace std;

vector<int> suffix_array(string &s) {
    // O(Nlog^2N)
    int n = s.size();
    vector<int> sa(n + 1), rank(n + 1), tmp(n + 1);
    for (int i = 0; i <= n; ++i) {
        sa[i]   = i;
        rank[i] = (i < n ? s[i] : -1);
    }
    for (int k = 1; k <= n; k <<= 1) {
        auto cmp = [&](int i, int j) {
            if (rank[i] != rank[j])
                return rank[i] < rank[j];
            else {
                int ri = (i + k <= n ? rank[i + k] : -1);
                int rj = (j + k <= n ? rank[j + k] : -1);
                return ri < rj;
            }
        };
        sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; ++i) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
        }
        for (int i = 0; i <= n; ++i) {
            rank[i] = tmp[i];
        }
    }
    return sa;
}

vector<int> lcp_array(string &s, vector<int> &sa) {
    int n = s.size();
    vector<int> rank(n);
    for (int i = 0; i < n; ++i) {
        rank[sa[i]] = i;
    }
}

Back to top page