Suffix Range Core

components/suffix_range.hpp · GitHub で見る

共通ページ

固定した本文の接尾辞配列上で、パターンの出現区間を結合・切り出しする内部部品です。DynamicPatternMatching の断片の照合に使います。編集可能なパターン全体の管理には DynamicPatternMatching を使います。

#include "lib/components/suffix_range.hpp"

int main() {
	SuffixRangeIndex index("banana");
	auto an = index.concat(index.character('a'), index.character('n'));
	auto ana = index.concat(an, index.character('a'));
	assert(ana.length == 3 && ana.right - ana.left == 2);
	assert(index.suffix_array()[ana.left] == 3);
	auto na = index.substring(ana, 1, 3);
	assert(na.length == 2 && na.right - na.left == 2);
	auto [prefix, length] = index.longest_prefix("anax");
	assert(length == 3 && prefix.left == ana.left && prefix.right == ana.right);
	assert(index.empty_range().right == 7);
}

Range は left・right・length の 3 つの int を持ちます。本文に現れるパターンについて、接尾辞配列上の [left,right) が全出現位置、length がパターンのバイト数です。出現回数は right-left、各出現位置は suffix_array()[left]～suffix_array()[right-1] です。位置の昇順ではありません。

本文に現れない場合は left == right となり、length は引き続きそのパターンの長さを表します。空パターンの区間には empty_range() を使います。空パターンは本文長を \(n\) として \(n+1\) 箇所に現れます。接尾辞配列は空の接尾辞を含み、先頭の値は n、配列長は n+1 です。

concat(a,b) は 2 つのパターンをこの順に連結した出現区間を返します。パターンそのものの文字列は不要です。substring(range,l,r) はパターン内の [l,r) を切り出します。切り出しには 元のパターンが本文に現れること が必要です。元の出現区間が空の場合は使えません。

longest_prefix(pattern) は、渡した文字列の先頭から本文に一致する最長の部分と、その長さを返します。パターン全体が現れなくても、途中まで一致した区間を返します。最初のバイトも一致しない場合は、空パターンの区間と長さ 0 です。

本文は内部にコピーします。NUL を含む全 256 バイトに対応し、辞書順は符号なしバイトの順です。本文長は INT_MAX/2 未満、concat 後のパターン長は INT_MAX 以下にしてください。Range は同じ索引から取得したものを渡し、フィールドを書き換えずに使います。

操作	内容・返り値	計算量
SuffixRangeIndex()	空の本文の索引を作る	\(O(1)\)
SuffixRangeIndex(text)	本文の索引を作る	\(O(n)\)
size() / text()	本文のバイト数 / 保存した本文の string_view	\(O(1)\)
suffix_array()	空の接尾辞を含む接尾辞配列への const 参照	\(O(1)\)
empty_range()	空パターンの区間	\(O(1)\)
character(c)	1 バイトのパターンの区間	\(O(1)\)
concat(a,b)	2 つのパターンを連結した区間	\(O(\log n)\)
substring(range,l,r)	一致するパターン内の半開区間を切り出す	\(O(\log n)\)
longest_prefix(pattern)	最長一致接頭辞の Range と長さの組	\(O(\ell)\)、不一致の判定は定数時間を加える
コピー構築・コピー代入	索引全体をコピー	\(O(n)\)。代入は旧領域の解放も加わる
ムーブ構築・ムーブ代入	索引を移動	構築 \(O(1)\)。代入は旧領域の解放も加わる

\(n\) は本文長、\(\ell\) は最長一致接頭辞の長さです。対数の項は本文長が 0・1 の場合に定数として扱います。substring には 0 <= l <= r <= range.length を渡します。構築時間・空間は \(O(n)\)。SA-IS、Suffix Tree、LCP 配列のセグメント木を使います。

依存ライブラリ

• Default Init Allocator
• 共通接頭辞・接尾辞の比較
• Static Range Min
• Suffix Array Core
• Sparse Table
• Suffix Tree (静的文字列)

検証コード

• test/dynamic_pattern_matching_array.test.cpp

コード

#ifndef SUFFIX_RANGE_HPP
#define SUFFIX_RANGE_HPP

#include "../string/suffix_tree.hpp"

class SuffixRangeIndex {
	SuffixTree tree_;
	std::vector<int> rank_, minimum_;
	int capacity_ = 1;
	int first_below(int v, int l, int r, int ql, int qr, int length) const {
		if (r <= ql || qr <= l || minimum_[v] >= length) return -1;
		if (r - l == 1) return l;
		int m = l + (r - l) / 2;
		int a = first_below(v * 2, l, m, ql, qr, length);
		return a == -1 ? first_below(v * 2 + 1, m, r, ql, qr, length) : a;
	}
	int last_below(int v, int l, int r, int ql, int qr, int length) const {
		if (r <= ql || qr <= l || minimum_[v] >= length) return -1;
		if (r - l == 1) return l;
		int m = l + (r - l) / 2;
		int a = last_below(v * 2 + 1, m, r, ql, qr, length);
		return a == -1 ? last_below(v * 2, l, m, ql, qr, length) : a;
	}

  public:
	struct Range { int left = 0, right = 0, length = 0; };
	SuffixRangeIndex() : SuffixRangeIndex(std::string_view{}) {}
	explicit SuffixRangeIndex(std::string_view text) : tree_(text) {
		int n = tree_.size();
		rank_.resize(n + 1);
		for (int i = 0; i <= n; ++i) rank_[suffix_array()[i]] = i;
		while (capacity_ < n) capacity_ *= 2;
		minimum_.assign(std::size_t(capacity_) * 2, std::numeric_limits<int>::max());
		std::copy(tree_.lcp_array().begin(), tree_.lcp_array().end(), minimum_.begin() + capacity_);
		for (int i = capacity_ - 1; i; --i) minimum_[i] = std::min(minimum_[i * 2], minimum_[i * 2 + 1]);
	}
	int size() const { return tree_.size(); }
	std::string_view text() const { return tree_.text(); }
	const std::vector<int> &suffix_array() const { return tree_.suffix_array(); }
	Range empty_range() const { return {0, size() + 1, 0}; }
	Range character(char c) const {
		int v = tree_.transition(0, c);
		if (v == -1) return {0, 0, 1};
		auto [l, r] = tree_.occurrence_range(v);
		return {l, r, 1};
	}
	Range concat(Range a, Range b) const {
		if (!a.length) return b;
		if (!b.length) return a;
		assert(a.length <= std::numeric_limits<int>::max() - b.length);
		Range missing{0, 0, a.length + b.length};
		if (a.left == a.right || b.left == b.right || a.length > size() - b.length) return missing;
		auto bound = [&](int target, int l) {
			int r = a.right;
			while (l < r) {
				int m = l + (r - l) / 2;
				if (rank_[suffix_array()[m] + a.length] < target) l = m + 1;
				else r = m;
			}
			return l;
		};
		int l = bound(b.left, a.left), r = bound(b.right, l);
		return l == r ? missing : Range{l, r, a.length + b.length};
	}
	Range substring(Range range, int l, int r) const {
		assert(0 <= l && l <= r && r <= range.length && range.left < range.right);
		if (l == r) return empty_range();
		int i = rank_[suffix_array()[range.left] + l], length = r - l;
		int a = last_below(1, 0, capacity_, 0, i, length) + 1;
		int b = first_below(1, 0, capacity_, i, size(), length);
		return {a, b == -1 ? size() + 1 : b + 1, length};
	}
	std::pair<Range, int> longest_prefix(std::string_view pattern) const {
		SuffixTree::Locus locus{0, 0};
		for (char c : pattern) {
			auto next = tree_.advance(locus, c);
			if (!next) break;
			locus = *next;
		}
		auto [l, r] = tree_.occurrence_range(locus.node);
		return {Range{l, r, locus.length}, locus.length};
	}
};

#endif

Back to top page