トライ木 (trie)
(include/emthrm/string/trie.hpp)
複数の文字列を高速に検索できる木である。
時間計算量
$O(\lvert S \rvert)$
仕様
template <int Sigma = 26>
struct Trie;
メンバ変数
| 名前 |
説明 |
const std::function<int(const char)> convert |
文字を数に変換する関数 |
std::vector<Node> nodes |
トライ木の頂点 |
メンバ関数
| 名前 |
効果・戻り値 |
|
explicit Trie(const std::function<int(const char)> convert = [](const char c) -> int { return c - 'a'; }); |
コンストラクタ |
|
void add(const std::string& s, const int id = -1, int pos = 0); |
$\mathrm{pos}$ 番目のノードから ID $\mathrm{id}$ の文字列 $S$ を追加する。 |
|
int find(const std::string& t, int pos = 0) const; |
$\mathrm{pos}$ 番目のノードから見たとき、文字列 $T$ に対応するノードのインデックス。ただし存在しないときは $-1$ を返す。 |
|
メンバ型
メンバ変数
| 名前 |
説明 |
char c |
そのノードが表す文字 |
std::array<int, Sigma> nxt |
子のインデックス |
std::vector<int> tails |
そのノードを末尾とする文字列の ID 集合 |
メンバ関数
| 名前 |
効果 |
explicit Node(const char c); |
コンストラクタ |
参考文献
- Edward Fredkin: Trie Memory, Communications of the ACM, Vol. 3, No. 9, pp. 490–499 (1960). https://doi.org/10.1145/367390.367400
- https://github.com/beet-aizu/library/blob/2ecdc969043f5276c3782a7752592bd3fe856524/string/trie.cpp
TODO
- 永続 trie
- https://ei1333.github.io/luzhiled/snippets/structure/binary-trie.html
Submissons
https://yukicoder.me/submissions/413744
Required by
Verified with
Code
#ifndef EMTHRM_STRING_TRIE_HPP_
#define EMTHRM_STRING_TRIE_HPP_
#include <algorithm>
#include <array>
#include <functional>
#include <string>
#include <vector>
namespace emthrm {
template <int Sigma = 26>
struct Trie {
struct Node {
char c;
std::array<int, Sigma> nxt;
std::vector<int> tails;
explicit Node(const char c) : c(c) {
std::fill(nxt.begin(), nxt.end(), -1);
}
};
const std::function<int(const char)> convert;
std::vector<Node> nodes;
explicit Trie(const std::function<int(const char)> convert =
[](const char c) -> int { return c - 'a'; })
: convert(convert) { nodes.emplace_back('$'); }
void add(const std::string& s, const int id = -1, int pos = 0) {
for (const char c : s) {
const int c_int = convert(c);
if (nodes[pos].nxt[c_int] == -1) {
const int nxt_pos = nodes.size();
nodes[pos].nxt[c_int] = nxt_pos;
nodes.emplace_back(c);
pos = nxt_pos;
} else {
pos = nodes[pos].nxt[c_int];
}
}
nodes[pos].tails.emplace_back(id);
}
int find(const std::string& t, int pos = 0) const {
for (const char c : t) {
const int c_int = convert(c);
if (nodes[pos].nxt[c_int] == -1) return -1;
pos = nodes[pos].nxt[c_int];
}
return pos;
}
};
} // namespace emthrm
#endif // EMTHRM_STRING_TRIE_HPP_
#line 1 "include/emthrm/string/trie.hpp"
#include <algorithm>
#include <array>
#include <functional>
#include <string>
#include <vector>
namespace emthrm {
template <int Sigma = 26>
struct Trie {
struct Node {
char c;
std::array<int, Sigma> nxt;
std::vector<int> tails;
explicit Node(const char c) : c(c) {
std::fill(nxt.begin(), nxt.end(), -1);
}
};
const std::function<int(const char)> convert;
std::vector<Node> nodes;
explicit Trie(const std::function<int(const char)> convert =
[](const char c) -> int { return c - 'a'; })
: convert(convert) { nodes.emplace_back('$'); }
void add(const std::string& s, const int id = -1, int pos = 0) {
for (const char c : s) {
const int c_int = convert(c);
if (nodes[pos].nxt[c_int] == -1) {
const int nxt_pos = nodes.size();
nodes[pos].nxt[c_int] = nxt_pos;
nodes.emplace_back(c);
pos = nxt_pos;
} else {
pos = nodes[pos].nxt[c_int];
}
}
nodes[pos].tails.emplace_back(id);
}
int find(const std::string& t, int pos = 0) const {
for (const char c : t) {
const int c_int = convert(c);
if (nodes[pos].nxt[c_int] == -1) return -1;
pos = nodes[pos].nxt[c_int];
}
return pos;
}
};
} // namespace emthrm
Back to top page