Trie

string/trie.hpp · GitHub で見る

共通ページ

文字列の重複付き集合を管理します。接頭辞ごとの個数、辞書順の順位・選択、LCP の集計に加え、各頂点に任意のデータを持たせて木 DP に使えます。

#include "lib/string/trie.hpp"

Trie<> trie;
int apple = trie.insert("apple", 2);
trie.insert("app");
trie.insert("bat");
assert(trie.size() == 4 && trie.distinct_size() == 3);
assert(trie.count("apple") == 2);
assert(trie.prefix_count("ap") == 3);
assert(trie.kth(1).value() == "apple"); // 0 始まり。重複も数える
assert(trie.order_of_key("bat") == 3);
assert(trie.lcp("apply") == 4);
assert(trie.lcp_sum("apply") == 11);   // 4+4+3+0
assert(trie.restore(apple) == "apple");
trie.erase("apple");                 // 1 個削除

Trie<Alphabet,First,Data> の既定値は英小文字 26 文字と追加データなしです。Trie<2,'A'> は A,B、Trie<10,'0'> は数字、Trie<256,0> は全 256 バイトに対応します。文字は [First,First+Alphabet) の範囲とし、辞書順は符号なしバイトの昇順です。空文字列も登録できます。

操作	内容・返り値	計算量
`Trie()` / `clear()`	空の Trie を作成／全ての頂点・登録・追加データを初期化	\(O(\sigma)\) / \(O(V+\sigma)\)
`reserve(total_length)`	文字数の合計を目安に頂点の領域を予約	\(O(V\sigma)\)
`insert(s,copies=1)`	`s` を `copies` 個追加し、終端頂点を返す	償却 \(O(L+K\sigma)\)
`erase(s,copies=1)`	指定個数を削除。足りなければ変更せず `false`	\(O(L)\)
`count(s)` / `contains(s)`	完全一致する個数／登録されているか	\(O(L)\)
`prefix_count(s)`	`s` を接頭辞に持つ登録文字列の個数	\(O(L)\)
`size()` / `distinct_size()` / `empty()`	重複込みの個数／異なる文字列数／未登録か	\(O(1)\)
`for_each_prefix(s,visit)`	`s` の接頭辞として登録された各終端頂点に `visit(v)`。短い順、重複はまとめて 1 回	\(O(L)\)
`longest_prefix(s)`	`s` の接頭辞として登録された最長の文字列の頂点。なければ `-1`	\(O(L)\)
`lcp(s)`	`s` と登録文字列の LCP 長の最大値。未登録なら `0`	\(O(L)\)
`lcp_sum(s)`	`s` と全登録文字列の LCP 長の総和。重複も数える	\(O(L)\)
`order_of_key(s)`	`s` より辞書順で小さい登録文字列の個数	\(O(L\sigma)\)
`kth_node(k)`	辞書順で 0 始まり `k` 番目の終端頂点。重複も数え、範囲外なら `-1`	\(O(H\sigma)\)
`kth(k)`	同じ選択結果を `optional<string>` で返す。範囲外なら `nullopt`	\(O(H\sigma)\)
`lower_bound(s)`	`s` 以上で最小の登録文字列を `optional<string>` で返す	\(O((L+H)\sigma)\)

copies は正としてください。個数と LCP 長の総和は符号付きの int64_t です。個数・総和がその範囲を超える場合は std::overflow_error を送出します。追加する文字列は指定した文字範囲内とし、検索文字列には範囲外のバイトも使えます。NUL を含む文字列は string または長さを指定した string_view で渡してください。

頂点番号は根が 0、新しい接頭辞が作られた順に増えます。同じ文字列の追加では同じ終端頂点を返します。削除しても頂点と追加データは残り、再追加でも同じ番号を使います。clear() 以外では既存の頂点番号は変わりません。

頂点を扱う操作	内容・返り値	計算量
`root` / `node_count()`	根の頂点番号 `0`／根を含む頂点数	\(O(1)\)
`ensure(s)`	経路だけを作り、終端頂点を返す。登録数は増やさない	償却 \(O(L+K\sigma)\)
`find(s)` / `walk(v,s)`	根／頂点 `v` から `s` をたどった頂点。経路がなければ `-1`	\(O(L)\)
`child(v,c)`	文字 `c` に対応する子。存在しない、または範囲外なら `-1`	\(O(1)\)
`children(v)`	各文字の子の `const array<int,Alphabet>&`。添字は `c-First`、欠けた子は `-1`	\(O(1)\)
`parent(v)` / `depth(v)` / `letter(v)`	親／接頭辞の長さ／親からの文字。根の親は `-1`、根に `letter` は使えない	\(O(1)\)
`terminal_count(v)`	頂点 `v` で終わる登録文字列の個数	\(O(1)\)
`prefix_count(v)`	頂点 `v` の部分木の登録文字列数。自身も含む	\(O(1)\)
`insert_node(v,copies=1)` / `erase_node(v,copies=1)`	既存頂点の文字列を追加／削除。返り値は `insert`／`erase` と同じ	\(O(d)\)
`restore(v)`	頂点が表す接頭辞を `string` で返す	\(O(d)\)
`data(v)`	頂点の追加データを `Data&` で取得。const Trie では `const Data&`	\(O(1)\)
`for_each_ancestor(v,visit)`	`v` から根まで、下から順に `visit(u)` を呼ぶ。自身と根を含む	\(O(d)\)

find・child・children は構造を参照する操作です。登録されているかは contains・terminal_count、その接頭辞の文字列が残っているかは prefix_count で判定してください。ensure だけで作った経路や、全て削除した後の経路も参照できます。

Data は初期化可能で、vector に格納できる型とします。各頂点の初期値は Data{} です。登録・削除で個数は自動更新しますが、追加データの計算は利用者が行います。コールバック内では data(v) を変更できます。走査中の文字列の追加・削除・clear() は行わないでください。data・children の参照は、頂点追加や reserve による再確保・clear()・代入・破棄で無効になります。

表の \(L\) は引数の文字列長、\(H\) は選ばれた文字列長、\(d\) は対象頂点の深さ、\(K\) は新しく作る頂点数、\(V\) は根を含む頂点数、\(\sigma\) は Alphabet です。Data の初期化・移動・破棄を定数時間としています。頂点数は INT_MAX 以下、保持する領域は \(O(V\sigma)\) です。再帰は使いません。

検証コード

test/trie.test.cpp

コード

#line 1 "string/trie.hpp"

#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <optional>
#include <stdexcept>
#include <string>
#include <string_view>
#include <vector>

namespace trie_detail {
struct Empty {};
}

template<int Alphabet = 26, int First = 'a', class Data = trie_detail::Empty>
class Trie {
	static_assert(0 < Alphabet && 0 <= First && First <= 255 && Alphabet <= 256 - First);
	struct Node {
		std::array<int, Alphabet> next;
		int parent, depth;
		char letter;
		std::int64_t count = 0, terminal = 0;
		[[no_unique_address]] Data data{};
		Node(int p = -1, int d = 0, char c = 0) : parent(p), depth(d), letter(c) { next.fill(-1); }
	};
	std::vector<Node> nodes_;
	int distinct_ = 0;
	static int symbol_(char c) { return int(static_cast<unsigned char>(c)) - First; }
	void check_([[maybe_unused]] int v) const { assert(0 <= v && v < node_count()); }
	void check_count_(std::int64_t copies) const {
		assert(copies > 0);
		if (copies > std::numeric_limits<std::int64_t>::max() - size()) throw std::overflow_error("Trie count");
	}
	int add_(int v, std::int64_t copies) {
		if (!nodes_[v].terminal) ++distinct_;
		nodes_[v].terminal += copies;
		for (int u = v; u != -1; u = nodes_[u].parent) nodes_[u].count += copies;
		return v;
	}
	template<class F>
	int walk_prefixes_(std::string_view s, F &&visit) const {
		int v = root;
		for (char c : s) {
			int u = child(v, c);
			if (u == -1 || !nodes_[u].count) break;
			v = u;
			visit(v);
		}
		return v;
	}

public:
	static constexpr int root = 0;
	Trie() { nodes_.emplace_back(); }
	std::int64_t size() const { return nodes_[root].count; }
	bool empty() const { return size() == 0; }
	int distinct_size() const { return distinct_; }
	int node_count() const { return static_cast<int>(nodes_.size()); }
	void reserve(int total_length) {
		assert(0 <= total_length && total_length < std::numeric_limits<int>::max());
		nodes_.reserve(std::size_t(total_length) + 1);
	}
	void clear() { nodes_.clear(), nodes_.emplace_back(); distinct_ = 0; }
	int ensure(std::string_view s) {
		assert(s.size() < std::size_t(std::numeric_limits<int>::max()));
		int v = root;
		for (char c : s) {
			int x = symbol_(c);
			assert(0 <= x && x < Alphabet);
			int u = nodes_[v].next[x];
			if (u == -1) {
				assert(node_count() < std::numeric_limits<int>::max());
				u = node_count();
				nodes_.emplace_back(v, nodes_[v].depth + 1, c);
				nodes_[v].next[x] = u;
			}
			v = u;
		}
		return v;
	}
	int insert(std::string_view s, std::int64_t copies = 1) {
		check_count_(copies);
		return add_(ensure(s), copies);
	}
	int insert_node(int v, std::int64_t copies = 1) {
		check_(v), check_count_(copies);
		return add_(v, copies);
	}
	bool erase_node(int v, std::int64_t copies = 1) {
		check_(v), assert(copies > 0);
		if (nodes_[v].terminal < copies) return false;
		nodes_[v].terminal -= copies;
		if (!nodes_[v].terminal) --distinct_;
		for (int u = v; u != -1; u = nodes_[u].parent) nodes_[u].count -= copies;
		return true;
	}
	bool erase(std::string_view s, std::int64_t copies = 1) {
		assert(copies > 0);
		int v = find(s);
		return v != -1 && erase_node(v, copies);
	}
	int parent(int v) const { check_(v); return nodes_[v].parent; }
	int depth(int v) const { check_(v); return nodes_[v].depth; }
	char letter(int v) const { check_(v); assert(v != root); return nodes_[v].letter; }
	const std::array<int, Alphabet> &children(int v) const { check_(v); return nodes_[v].next; }
	int child(int v, char c) const {
		check_(v);
		int x = symbol_(c);
		return 0 <= x && x < Alphabet ? nodes_[v].next[x] : -1;
	}
	std::int64_t terminal_count(int v) const { check_(v); return nodes_[v].terminal; }
	std::int64_t prefix_count(int v) const { check_(v); return nodes_[v].count; }
	Data &data(int v) { check_(v); return nodes_[v].data; }
	const Data &data(int v) const { check_(v); return nodes_[v].data; }
	int walk(int v, std::string_view s) const {
		check_(v);
		for (char c : s) { v = child(v, c); if (v == -1) break; }
		return v;
	}
	int find(std::string_view s) const { return walk(root, s); }
	std::int64_t count(std::string_view s) const { int v = find(s); return v == -1 ? 0 : nodes_[v].terminal; }
	bool contains(std::string_view s) const { return count(s) != 0; }
	std::int64_t prefix_count(std::string_view s) const { int v = find(s); return v == -1 ? 0 : nodes_[v].count; }
	std::string restore(int v) const {
		check_(v);
		std::string s(nodes_[v].depth, '\0');
		for (int i = int(s.size()); i > 0; v = nodes_[v].parent) s[--i] = nodes_[v].letter;
		return s;
	}
	template<class F>
	void for_each_ancestor(int v, F &&visit) const {
		check_(v);
		for (; v != -1; v = nodes_[v].parent) visit(v);
	}
	template<class F>
	void for_each_prefix(std::string_view s, F &&visit) const {
		if (nodes_[root].terminal) visit(root);
		walk_prefixes_(s, [&](int v) {
			if (nodes_[v].terminal) visit(v);
		});
	}
	int longest_prefix(std::string_view s) const {
		int v = -1;
		for_each_prefix(s, [&](int u) { v = u; });
		return v;
	}
	int lcp(std::string_view s) const {
		return nodes_[walk_prefixes_(s, [](int) {})].depth;
	}
	std::int64_t lcp_sum(std::string_view s) const {
		std::int64_t sum = 0;
		walk_prefixes_(s, [&](int v) {
			if (nodes_[v].count > std::numeric_limits<std::int64_t>::max() - sum) throw std::overflow_error("Trie LCP sum");
			sum += nodes_[v].count;
		});
		return sum;
	}
	std::int64_t order_of_key(std::string_view s) const {
		int v = root;
		std::int64_t rank = 0;
		for (char c : s) {
			rank += nodes_[v].terminal;
			int x = symbol_(c);
			for (int j = 0; j < Alphabet && j < x; ++j) {
				int u = nodes_[v].next[j];
				if (u != -1) rank += nodes_[u].count;
			}
			if (x < 0 || x >= Alphabet) break;
			v = nodes_[v].next[x];
			if (v == -1) break;
		}
		return rank;
	}
	int kth_node(std::int64_t k) const {
		if (k < 0 || k >= size()) return -1;
		int v = root;
		while (true) {
			if (k < nodes_[v].terminal) return v;
			k -= nodes_[v].terminal;
			for (int u : nodes_[v].next) if (u != -1) {
				if (k < nodes_[u].count) { v = u; break; }
				k -= nodes_[u].count;
			}
		}
	}
	std::optional<std::string> kth(std::int64_t k) const {
		int v = kth_node(k);
		return v == -1 ? std::nullopt : std::optional<std::string>(restore(v));
	}
	std::optional<std::string> lower_bound(std::string_view s) const { return kth(order_of_key(s)); }
};

#ifndef TRIE_HPP
#define TRIE_HPP

#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <optional>
#include <stdexcept>
#include <string>
#include <string_view>
#include <vector>

namespace trie_detail {
struct Empty {};
}

template<int Alphabet = 26, int First = 'a', class Data = trie_detail::Empty>
class Trie {
	static_assert(0 < Alphabet && 0 <= First && First <= 255 && Alphabet <= 256 - First);
	struct Node {
		std::array<int, Alphabet> next;
		int parent, depth;
		char letter;
		std::int64_t count = 0, terminal = 0;
		[[no_unique_address]] Data data{};
		Node(int p = -1, int d = 0, char c = 0) : parent(p), depth(d), letter(c) { next.fill(-1); }
	};
	std::vector<Node> nodes_;
	int distinct_ = 0;
	static int symbol_(char c) { return int(static_cast<unsigned char>(c)) - First; }
	void check_([[maybe_unused]] int v) const { assert(0 <= v && v < node_count()); }
	void check_count_(std::int64_t copies) const {
		assert(copies > 0);
		if (copies > std::numeric_limits<std::int64_t>::max() - size()) throw std::overflow_error("Trie count");
	}
	int add_(int v, std::int64_t copies) {
		if (!nodes_[v].terminal) ++distinct_;
		nodes_[v].terminal += copies;
		for (int u = v; u != -1; u = nodes_[u].parent) nodes_[u].count += copies;
		return v;
	}
	template<class F>
	int walk_prefixes_(std::string_view s, F &&visit) const {
		int v = root;
		for (char c : s) {
			int u = child(v, c);
			if (u == -1 || !nodes_[u].count) break;
			v = u;
			visit(v);
		}
		return v;
	}

  public:
	static constexpr int root = 0;
	Trie() { nodes_.emplace_back(); }
	std::int64_t size() const { return nodes_[root].count; }
	bool empty() const { return size() == 0; }
	int distinct_size() const { return distinct_; }
	int node_count() const { return static_cast<int>(nodes_.size()); }
	void reserve(int total_length) {
		assert(0 <= total_length && total_length < std::numeric_limits<int>::max());
		nodes_.reserve(std::size_t(total_length) + 1);
	}
	void clear() { nodes_.clear(), nodes_.emplace_back(); distinct_ = 0; }
	int ensure(std::string_view s) {
		assert(s.size() < std::size_t(std::numeric_limits<int>::max()));
		int v = root;
		for (char c : s) {
			int x = symbol_(c);
			assert(0 <= x && x < Alphabet);
			int u = nodes_[v].next[x];
			if (u == -1) {
				assert(node_count() < std::numeric_limits<int>::max());
				u = node_count();
				nodes_.emplace_back(v, nodes_[v].depth + 1, c);
				nodes_[v].next[x] = u;
			}
			v = u;
		}
		return v;
	}
	int insert(std::string_view s, std::int64_t copies = 1) {
		check_count_(copies);
		return add_(ensure(s), copies);
	}
	int insert_node(int v, std::int64_t copies = 1) {
		check_(v), check_count_(copies);
		return add_(v, copies);
	}
	bool erase_node(int v, std::int64_t copies = 1) {
		check_(v), assert(copies > 0);
		if (nodes_[v].terminal < copies) return false;
		nodes_[v].terminal -= copies;
		if (!nodes_[v].terminal) --distinct_;
		for (int u = v; u != -1; u = nodes_[u].parent) nodes_[u].count -= copies;
		return true;
	}
	bool erase(std::string_view s, std::int64_t copies = 1) {
		assert(copies > 0);
		int v = find(s);
		return v != -1 && erase_node(v, copies);
	}
	int parent(int v) const { check_(v); return nodes_[v].parent; }
	int depth(int v) const { check_(v); return nodes_[v].depth; }
	char letter(int v) const { check_(v); assert(v != root); return nodes_[v].letter; }
	const std::array<int, Alphabet> &children(int v) const { check_(v); return nodes_[v].next; }
	int child(int v, char c) const {
		check_(v);
		int x = symbol_(c);
		return 0 <= x && x < Alphabet ? nodes_[v].next[x] : -1;
	}
	std::int64_t terminal_count(int v) const { check_(v); return nodes_[v].terminal; }
	std::int64_t prefix_count(int v) const { check_(v); return nodes_[v].count; }
	Data &data(int v) { check_(v); return nodes_[v].data; }
	const Data &data(int v) const { check_(v); return nodes_[v].data; }
	int walk(int v, std::string_view s) const {
		check_(v);
		for (char c : s) { v = child(v, c); if (v == -1) break; }
		return v;
	}
	int find(std::string_view s) const { return walk(root, s); }
	std::int64_t count(std::string_view s) const { int v = find(s); return v == -1 ? 0 : nodes_[v].terminal; }
	bool contains(std::string_view s) const { return count(s) != 0; }
	std::int64_t prefix_count(std::string_view s) const { int v = find(s); return v == -1 ? 0 : nodes_[v].count; }
	std::string restore(int v) const {
		check_(v);
		std::string s(nodes_[v].depth, '\0');
		for (int i = int(s.size()); i > 0; v = nodes_[v].parent) s[--i] = nodes_[v].letter;
		return s;
	}
	template<class F>
	void for_each_ancestor(int v, F &&visit) const {
		check_(v);
		for (; v != -1; v = nodes_[v].parent) visit(v);
	}
	template<class F>
	void for_each_prefix(std::string_view s, F &&visit) const {
		if (nodes_[root].terminal) visit(root);
		walk_prefixes_(s, [&](int v) {
			if (nodes_[v].terminal) visit(v);
		});
	}
	int longest_prefix(std::string_view s) const {
		int v = -1;
		for_each_prefix(s, [&](int u) { v = u; });
		return v;
	}
	int lcp(std::string_view s) const {
		return nodes_[walk_prefixes_(s, [](int) {})].depth;
	}
	std::int64_t lcp_sum(std::string_view s) const {
		std::int64_t sum = 0;
		walk_prefixes_(s, [&](int v) {
			if (nodes_[v].count > std::numeric_limits<std::int64_t>::max() - sum) throw std::overflow_error("Trie LCP sum");
			sum += nodes_[v].count;
		});
		return sum;
	}
	std::int64_t order_of_key(std::string_view s) const {
		int v = root;
		std::int64_t rank = 0;
		for (char c : s) {
			rank += nodes_[v].terminal;
			int x = symbol_(c);
			for (int j = 0; j < Alphabet && j < x; ++j) {
				int u = nodes_[v].next[j];
				if (u != -1) rank += nodes_[u].count;
			}
			if (x < 0 || x >= Alphabet) break;
			v = nodes_[v].next[x];
			if (v == -1) break;
		}
		return rank;
	}
	int kth_node(std::int64_t k) const {
		if (k < 0 || k >= size()) return -1;
		int v = root;
		while (true) {
			if (k < nodes_[v].terminal) return v;
			k -= nodes_[v].terminal;
			for (int u : nodes_[v].next) if (u != -1) {
				if (k < nodes_[u].count) { v = u; break; }
				k -= nodes_[u].count;
			}
		}
	}
	std::optional<std::string> kth(std::int64_t k) const {
		int v = kth_node(k);
		return v == -1 ? std::nullopt : std::optional<std::string>(restore(v));
	}
	std::optional<std::string> lower_bound(std::string_view s) const { return kth(order_of_key(s)); }
};

#endif

#line 1 "string/trie.hpp"



#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <optional>
#include <stdexcept>
#include <string>
#include <string_view>
#include <vector>

namespace trie_detail {
struct Empty {};
}

template<int Alphabet = 26, int First = 'a', class Data = trie_detail::Empty>
class Trie {
	static_assert(0 < Alphabet && 0 <= First && First <= 255 && Alphabet <= 256 - First);
	struct Node {
		std::array<int, Alphabet> next;
		int parent, depth;
		char letter;
		std::int64_t count = 0, terminal = 0;
		[[no_unique_address]] Data data{};
		Node(int p = -1, int d = 0, char c = 0) : parent(p), depth(d), letter(c) { next.fill(-1); }
	};
	std::vector<Node> nodes_;
	int distinct_ = 0;
	static int symbol_(char c) { return int(static_cast<unsigned char>(c)) - First; }
	void check_([[maybe_unused]] int v) const { assert(0 <= v && v < node_count()); }
	void check_count_(std::int64_t copies) const {
		assert(copies > 0);
		if (copies > std::numeric_limits<std::int64_t>::max() - size()) throw std::overflow_error("Trie count");
	}
	int add_(int v, std::int64_t copies) {
		if (!nodes_[v].terminal) ++distinct_;
		nodes_[v].terminal += copies;
		for (int u = v; u != -1; u = nodes_[u].parent) nodes_[u].count += copies;
		return v;
	}
	template<class F>
	int walk_prefixes_(std::string_view s, F &&visit) const {
		int v = root;
		for (char c : s) {
			int u = child(v, c);
			if (u == -1 || !nodes_[u].count) break;
			v = u;
			visit(v);
		}
		return v;
	}

  public:
	static constexpr int root = 0;
	Trie() { nodes_.emplace_back(); }
	std::int64_t size() const { return nodes_[root].count; }
	bool empty() const { return size() == 0; }
	int distinct_size() const { return distinct_; }
	int node_count() const { return static_cast<int>(nodes_.size()); }
	void reserve(int total_length) {
		assert(0 <= total_length && total_length < std::numeric_limits<int>::max());
		nodes_.reserve(std::size_t(total_length) + 1);
	}
	void clear() { nodes_.clear(), nodes_.emplace_back(); distinct_ = 0; }
	int ensure(std::string_view s) {
		assert(s.size() < std::size_t(std::numeric_limits<int>::max()));
		int v = root;
		for (char c : s) {
			int x = symbol_(c);
			assert(0 <= x && x < Alphabet);
			int u = nodes_[v].next[x];
			if (u == -1) {
				assert(node_count() < std::numeric_limits<int>::max());
				u = node_count();
				nodes_.emplace_back(v, nodes_[v].depth + 1, c);
				nodes_[v].next[x] = u;
			}
			v = u;
		}
		return v;
	}
	int insert(std::string_view s, std::int64_t copies = 1) {
		check_count_(copies);
		return add_(ensure(s), copies);
	}
	int insert_node(int v, std::int64_t copies = 1) {
		check_(v), check_count_(copies);
		return add_(v, copies);
	}
	bool erase_node(int v, std::int64_t copies = 1) {
		check_(v), assert(copies > 0);
		if (nodes_[v].terminal < copies) return false;
		nodes_[v].terminal -= copies;
		if (!nodes_[v].terminal) --distinct_;
		for (int u = v; u != -1; u = nodes_[u].parent) nodes_[u].count -= copies;
		return true;
	}
	bool erase(std::string_view s, std::int64_t copies = 1) {
		assert(copies > 0);
		int v = find(s);
		return v != -1 && erase_node(v, copies);
	}
	int parent(int v) const { check_(v); return nodes_[v].parent; }
	int depth(int v) const { check_(v); return nodes_[v].depth; }
	char letter(int v) const { check_(v); assert(v != root); return nodes_[v].letter; }
	const std::array<int, Alphabet> &children(int v) const { check_(v); return nodes_[v].next; }
	int child(int v, char c) const {
		check_(v);
		int x = symbol_(c);
		return 0 <= x && x < Alphabet ? nodes_[v].next[x] : -1;
	}
	std::int64_t terminal_count(int v) const { check_(v); return nodes_[v].terminal; }
	std::int64_t prefix_count(int v) const { check_(v); return nodes_[v].count; }
	Data &data(int v) { check_(v); return nodes_[v].data; }
	const Data &data(int v) const { check_(v); return nodes_[v].data; }
	int walk(int v, std::string_view s) const {
		check_(v);
		for (char c : s) { v = child(v, c); if (v == -1) break; }
		return v;
	}
	int find(std::string_view s) const { return walk(root, s); }
	std::int64_t count(std::string_view s) const { int v = find(s); return v == -1 ? 0 : nodes_[v].terminal; }
	bool contains(std::string_view s) const { return count(s) != 0; }
	std::int64_t prefix_count(std::string_view s) const { int v = find(s); return v == -1 ? 0 : nodes_[v].count; }
	std::string restore(int v) const {
		check_(v);
		std::string s(nodes_[v].depth, '\0');
		for (int i = int(s.size()); i > 0; v = nodes_[v].parent) s[--i] = nodes_[v].letter;
		return s;
	}
	template<class F>
	void for_each_ancestor(int v, F &&visit) const {
		check_(v);
		for (; v != -1; v = nodes_[v].parent) visit(v);
	}
	template<class F>
	void for_each_prefix(std::string_view s, F &&visit) const {
		if (nodes_[root].terminal) visit(root);
		walk_prefixes_(s, [&](int v) {
			if (nodes_[v].terminal) visit(v);
		});
	}
	int longest_prefix(std::string_view s) const {
		int v = -1;
		for_each_prefix(s, [&](int u) { v = u; });
		return v;
	}
	int lcp(std::string_view s) const {
		return nodes_[walk_prefixes_(s, [](int) {})].depth;
	}
	std::int64_t lcp_sum(std::string_view s) const {
		std::int64_t sum = 0;
		walk_prefixes_(s, [&](int v) {
			if (nodes_[v].count > std::numeric_limits<std::int64_t>::max() - sum) throw std::overflow_error("Trie LCP sum");
			sum += nodes_[v].count;
		});
		return sum;
	}
	std::int64_t order_of_key(std::string_view s) const {
		int v = root;
		std::int64_t rank = 0;
		for (char c : s) {
			rank += nodes_[v].terminal;
			int x = symbol_(c);
			for (int j = 0; j < Alphabet && j < x; ++j) {
				int u = nodes_[v].next[j];
				if (u != -1) rank += nodes_[u].count;
			}
			if (x < 0 || x >= Alphabet) break;
			v = nodes_[v].next[x];
			if (v == -1) break;
		}
		return rank;
	}
	int kth_node(std::int64_t k) const {
		if (k < 0 || k >= size()) return -1;
		int v = root;
		while (true) {
			if (k < nodes_[v].terminal) return v;
			k -= nodes_[v].terminal;
			for (int u : nodes_[v].next) if (u != -1) {
				if (k < nodes_[u].count) { v = u; break; }
				k -= nodes_[u].count;
			}
		}
	}
	std::optional<std::string> kth(std::int64_t k) const {
		int v = kth_node(k);
		return v == -1 ? std::nullopt : std::optional<std::string>(restore(v));
	}
	std::optional<std::string> lower_bound(std::string_view s) const { return kth(order_of_key(s)); }
};