Suffix Locus Index

components/suffix_locus.hpp · GitHub で見る

共通ページ

構築済みの SuffixTree に対して、本文中の半開区間 [l,r) が表す部分文字列の位置を求める内部部品です。文字列の比較や Rolling Hash を使わず、接尾辞の終点から重み付き祖先を検索します。

#include "lib/components/suffix_locus.hpp"

int main() {
	SuffixTree tree("banana");
	SuffixLocusIndex index(tree);
	auto locus = index.locate(1, 4);
	assert(locus.length == 3);
	assert(tree.occurrence_count(locus.node) == 2);
	auto same = index.locate(3, 6);
	assert(locus.node == same.node && locus.length == same.length);
	assert(index.locate(6, 6).node == SuffixTree::root);
}

locate(l,r) は SuffixTree::Locus を返します。node は部分文字列の終点が属する辺の行き先、length は r-l です。終点が頂点と一致するときはその頂点になります。区間には 0 <= l <= r <= size() を渡してください。空区間は位置にかかわらず {0,0}、同じ内容を持つ重複した部分文字列は同じ位置になります。本文の区間を指定するため、不在という結果はありません。

SuffixLocusIndex() はメモリを確保せず、空の本文に対応する索引を作ります。SuffixLocusIndex(const SuffixTree &tree) と build(const SuffixTree &tree) は、その時点の木の頂点番号・深さ・接尾辞の終点をコピーして索引を作ります。引数の既定値はありません。本文の長さとバイトの扱いは SuffixTree に従い、全 256 バイトに対応し、長さは INT_MAX/2 未満です。

索引は元の木への参照を保持せず、元の木の変更・破棄後も検索できます。ただし、返された頂点番号を木の操作に渡す場合は、索引の構築時と同じ頂点番号を保持する木を使ってください。別の本文から再構築した木には渡せません。build がメモリ確保に失敗した場合は元の索引を維持します。ムーブと swap は noexcept です。

操作	内容・返り値	計算量
SuffixLocusIndex()	空の索引	\(O(1)\)
SuffixLocusIndex(tree)	木から索引を構築	\(O(n)\)
build(tree)	木から再構築、返り値は void	\(O(n)\)、旧索引の解放時間も加わる
size()	本文長を int で返す	\(O(1)\)
locate(l,r)	区間の SuffixTree::Locus	\(O(\log n)\)、空区間は \(O(1)\)
swap(other)	2 つの索引を交換、返り値は void	\(O(1)\)
コピー構築・コピー代入	独立した索引を作る	\(O(n)\)、代入は旧索引の解放時間も加わる
ムーブ構築・ムーブ代入	索引を移し、移動元を空の索引に戻す	構築 \(O(1)\)、代入は旧索引の解放時間も加わる

\(n\) は本文長です。空入力と長さ 1 では検索時間を定数として扱います。構築時に SuffixTree の木構造がまだ生成されていなければ、その生成も行います。接尾辞配列は再構築せず、LCP・LCA 用の RMQ 索引も生成しません。出現数が最大の子を重い辺として選び、重い辺上の頂点を連続配置することで、構築時間・保持空間・構築時の補助空間はいずれも \(O(n)\) です。

依存ライブラリ

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

検証コード

• test/basic_substring_structure_substrings.test.cpp

コード

#ifndef SUFFIX_LOCUS_HPP
#define SUFFIX_LOCUS_HPP

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

class SuffixLocusIndex {
	struct Node { int parent, depth, head, vertex; };
	std::vector<Node> nodes_;
	std::vector<int> terminal_;

  public:
	SuffixLocusIndex() = default;
	explicit SuffixLocusIndex(const SuffixTree &tree) { build(tree); }
	SuffixLocusIndex(const SuffixLocusIndex &) = default;
	SuffixLocusIndex &operator=(const SuffixLocusIndex &) = default;
	SuffixLocusIndex(SuffixLocusIndex &&other) noexcept { swap(other); }
	SuffixLocusIndex &operator=(SuffixLocusIndex &&other) noexcept {
		if (this != &other) { SuffixLocusIndex moved(std::move(other)); swap(moved); }
		return *this;
	}
	void swap(SuffixLocusIndex &other) noexcept {
		nodes_.swap(other.nodes_);
		terminal_.swap(other.terminal_);
	}
	void build(const SuffixTree &tree) {
		SuffixLocusIndex result;
		int count = tree.node_count();
		std::vector<int> heavy(count, -1), position(count);
		for (int v = 0; v < count; ++v)
			for (int u : tree.children(v))
				if (heavy[v] == -1 || tree.occurrence_count(u) > tree.occurrence_count(heavy[v])) heavy[v] = u;
		result.nodes_.clear();
		result.nodes_.reserve(count);
		std::vector<std::pair<int, int>> stack{{0, -1}};
		while (!stack.empty()) {
			auto [v, parent] = stack.back();
			stack.pop_back();
			int head = int(result.nodes_.size());
			while (v != -1) {
				int i = int(result.nodes_.size());
				result.nodes_.push_back({parent, tree.depth(v), head, v});
				position[v] = i;
				for (int u : tree.children(v)) if (u != heavy[v]) stack.emplace_back(u, i);
				parent = i;
				v = heavy[v];
			}
		}
		result.terminal_.resize(std::size_t(tree.size()) + 1);
		for (int p = 0; p <= tree.size(); ++p) result.terminal_[p] = position[tree.suffix_node(p)];
		swap(result);
	}
	int size() const { return terminal_.empty() ? 0 : int(terminal_.size()) - 1; }
	SuffixTree::Locus locate(int l, int r) const {
		assert(0 <= l && l <= r && r <= size());
		int length = r - l;
		if (!length) return {0, 0};
		int v = terminal_[l];
		for (;;) {
			int p = nodes_[nodes_[v].head].parent;
			if (p == -1 || nodes_[p].depth < length) break;
			v = p;
		}
		int a = nodes_[v].head, b = v;
		while (a < b) {
			int m = a + (b - a) / 2;
			if (nodes_[m].depth < length) a = m + 1;
			else b = m;
		}
		return {nodes_[a].vertex, length};
	}
};

#endif

Back to top page