Suffix Array

string/suffix_array.hpp · GitHub で見る

共通ページ

#include "lib/string/suffix_array.hpp"
#include <cassert>

int main() {
	auto sa = suffix_array("banana");
	assert((sa == std::vector<int>{5, 3, 1, 0, 4, 2}));
}

関数	内容
suffix_array(s)	std::string_view、または std::vector<T> の空でない接尾辞を辞書順に並べ、その開始位置を std::vector<int> で返す
suffix_array(s, upper)	std::vector<int> を、各要素が 0 <= x <= upper の整数列として処理する。upper >= 0

長さは INT_MAX 以下です。空列は空配列、長さ 1 なら [0] を返します。文字列は符号なしバイト順です。一般の T は < による厳密弱順序が必要です。文字列と vector<char> は、高位ビットのある文字で順序が異なる場合があります。後者は char の大小関係に従います。

長さを \(n\) として、文字列版は \(O(n)\) 時間・空間、整数の値域を渡す版は \(O(n+\text{upper})\) 時間・空間、一般の列は \(O(n\log n)\) 時間、\(O(n)\) 空間です。upper > INT_MAX - 2 の場合は座標圧縮する版を使います。空列は定数時間・空間です。

依存ライブラリ

• Suffix Array Core

検証コード

• test/suffix_array_public.test.cpp

コード

#ifndef STRING_SUFFIX_ARRAY_HPP
#define STRING_SUFFIX_ARRAY_HPP

#include "../components/suffix_array.hpp"

inline std::vector<int> suffix_array(std::string_view s) { return suffix_array_detail::bytes(s); }

template <class T>
std::vector<int> suffix_array(const std::vector<T> &s) {
	assert(s.size() <= std::size_t(std::numeric_limits<int>::max()));
	std::vector<int> order(s.size()), ranks(s.size());
	std::iota(order.begin(), order.end(), 0);
	std::sort(order.begin(), order.end(), [&](int a, int b) { return s[a] < s[b]; });
	int rank = 0;
	for (std::size_t i = 0; i < order.size(); ++i) {
		if (i && s[order[i - 1]] < s[order[i]]) ++rank;
		ranks[order[i]] = rank;
	}
	return suffix_array_detail::induced_sort(ranks, rank);
}

inline std::vector<int> suffix_array(const std::vector<int> &s, int upper) {
	assert(upper >= 0 && s.size() <= std::size_t(std::numeric_limits<int>::max()));
	for ([[maybe_unused]] int x : s) assert(0 <= x && x <= upper);
	if (upper > std::numeric_limits<int>::max() - 2) return suffix_array(s);
	return suffix_array_detail::induced_sort(s, upper);
}

#endif

Back to top page