Suffix Array
(string/suffix_array.hpp)

• View this file on GitHub
• Last update: 2023-11-17 01:51:05+09:00
• Include: #include "string/suffix_array.hpp"

説明

ダブリングによってsuffix arrayを構築する。文字列長を $N$ とする。

suffix_array(string s)

s のsuffix arrayを構築する。 $O(N (\log N)^2)$

lcp_array(string s, vector sa)

s のlcp_arrayを構築する。 $O(N)$

Depends on

• テンプレート (template/template.hpp)

Verified with

• test/string/Number_of_Substrings.test.cpp
• test/string/Suffix_Array.test.cpp

Code

#pragma once

#include "../template/template.hpp"

namespace lib {

vector<int> suffix_array(const string &s) {
    int n = s.size();
    vector<int> rnk(n, -1), sa(n);
    iota(all(sa), 0);
    rep(i, 0, n) {
        rnk[i] = s[i];
    }
    int k = 1;
    auto compare = [&](int i, int j) -> bool {
        if (rnk[i] != rnk[j]) return rnk[i] < rnk[j];
        return (i + k < n ? rnk[i + k] : -1) < (j + k < n ? rnk[j + k] : -1);
    };
    while (k < n) {
        sort(all(sa), compare);
        vector<int> tmp(n, 0);
        rep(i, 1, n) {
            tmp[sa[i]] = tmp[sa[i - 1]] + int(compare(sa[i - 1], sa[i]));
        }
        swap(rnk, tmp);
        k <<= 1;
    }
    return sa;
}

vector<int> lcp_array(const string &s, const vector<int> &sa) {
    int n = s.size();
    vector<int> rnk(n), lcp(n - 1);
    rep(i, 0, n) rnk[sa[i]] = i;
    int h = 0;
    rep(i, 0, n) {
        if (h > 0) h--;
        if (rnk[i] == 0) continue;
        int j = sa[rnk[i] - 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) {
            h++;
        }
        lcp[rnk[i] - 1] = h;
    }
    return lcp;
}

}  // namespace lib

#line 2 "string/suffix_array.hpp"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 4 "string/suffix_array.hpp"

namespace lib {

vector<int> suffix_array(const string &s) {
    int n = s.size();
    vector<int> rnk(n, -1), sa(n);
    iota(all(sa), 0);
    rep(i, 0, n) {
        rnk[i] = s[i];
    }
    int k = 1;
    auto compare = [&](int i, int j) -> bool {
        if (rnk[i] != rnk[j]) return rnk[i] < rnk[j];
        return (i + k < n ? rnk[i + k] : -1) < (j + k < n ? rnk[j + k] : -1);
    };
    while (k < n) {
        sort(all(sa), compare);
        vector<int> tmp(n, 0);
        rep(i, 1, n) {
            tmp[sa[i]] = tmp[sa[i - 1]] + int(compare(sa[i - 1], sa[i]));
        }
        swap(rnk, tmp);
        k <<= 1;
    }
    return sa;
}

vector<int> lcp_array(const string &s, const vector<int> &sa) {
    int n = s.size();
    vector<int> rnk(n), lcp(n - 1);
    rep(i, 0, n) rnk[sa[i]] = i;
    int h = 0;
    rep(i, 0, n) {
        if (h > 0) h--;
        if (rnk[i] == 0) continue;
        int j = sa[rnk[i] - 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) {
            h++;
        }
        lcp[rnk[i] - 1] = h;
    }
    return lcp;
}

}  // namespace lib

Back to top page