LCP Array

string/lcp_array.hpp · GitHub で見る

共通ページ

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

int main() {
	std::string_view s = "banana";
	auto lcp = lcp_array(s, suffix_array(s));
	assert((lcp == std::vector<int>{1, 3, 0, 0, 2}));
}

lcp_array(s, sa) は、Suffix Array の隣り合う接尾辞の最長共通接頭辞長を std::vector<int> で返します。lcp[i] は s[sa[i]..] と s[sa[i+1]..] の共通接頭辞の長さです。

s は std::string_view または std::vector<T>、sa は std::vector<int> です。長さは INT_MAX 以下で、sa は同じ列の Suffix Array である必要があります。T は == に対応し、Suffix Array 構築時の等値関係と一致させてください。返り値の長さは、非空の列では s.size()-1 です。空列・長さ 1 の列では空配列を返します。

長さ \(n\) に対し \(O(n)\) 時間・追加空間です。空列は定数時間・空間です。

コード

#ifndef LCP_ARRAY_HPP
#define LCP_ARRAY_HPP

#include <algorithm>
#include <cassert>
#include <limits>
#include <string_view>
#include <vector>

namespace lcp_array_detail {
template <class Sequence>
std::vector<int> build(const Sequence &s, const std::vector<int> &sa) {
	assert(s.size() <= std::size_t(std::numeric_limits<int>::max()) && sa.size() == s.size());
	int n = int(s.size());
	if (!n) return {};
	std::vector<int> rank(n, -1), result(n - 1);
	for (int i = 0; i < n; ++i) {
		assert(0 <= sa[i] && sa[i] < n && rank[sa[i]] == -1);
		rank[sa[i]] = i;
	}
	for (int i = 0, h = 0; i < n; ++i) {
		if (h) --h;
		if (rank[i] == 0) { h = 0; continue; }
		int j = sa[rank[i] - 1];
		int limit = n - std::max(i, j);
		while (h < limit && s[i + h] == s[j + h]) ++h;
		result[rank[i] - 1] = h;
	}
	return result;
}
}

inline std::vector<int> lcp_array(std::string_view s, const std::vector<int> &sa) { return lcp_array_detail::build(s, sa); }
template <class T>
std::vector<int> lcp_array(const std::vector<T> &s, const std::vector<int> &sa) { return lcp_array_detail::build(s, sa); }

#endif

Back to top page