1 #include "hmbdc/Copyright.hpp" 4 #include <ext/pb_ds/assoc_container.hpp> 5 #include <ext/pb_ds/trie_policy.hpp> 11 namespace hmbdc {
namespace text {
16 using size_type = size_t;
17 using key_type = std::string;
18 using __rebind_k = std::allocator<char>::template rebind<key_type>;
19 using key_const_reference =
typename __rebind_k::other::const_reference;
20 enum { reverse =
false };
21 using const_iterator =
const char*;
22 using e_type =
const char;
25 min_e_val = __gnu_pbds::detail::__numeric_traits<char>::__min,
26 max_e_val = __gnu_pbds::detail::__numeric_traits<char>::__max,
27 max_size = max_e_val - min_e_val + 1
32 inline static const_iterator
33 begin(key_const_reference ck) {
return ck.c_str(); }
37 inline static const_iterator
38 end(key_const_reference ck) {
return ck.c_str() + ck.size(); }
41 inline static size_type
42 e_pos(e_type e) {
return static_cast<size_type
>(e - min_e_val); }
46 template<
typename Node_CItr,
53 : __gnu_pbds::detail::trie_policy_base<Node_CItr,Node_Itr,_ATraits, _Alloc> {
55 using base_type = __gnu_pbds::detail::trie_policy_base<Node_CItr, Node_Itr, _ATraits, _Alloc>;
56 using node_iterator =
typename base_type::node_iterator;
57 using node_const_iterator =
typename base_type::node_const_iterator;
58 using access_traits =
typename base_type::access_traits;
59 using size_type =
typename base_type::size_type;
62 search_recursive(Node_Itr nd_it, Node_Itr end_nd_it
63 ,
typename access_traits::const_iterator b
64 ,
typename access_traits::const_iterator e
66 if (nd_it == end_nd_it) {
69 auto r = nd_it.valid_prefix();
70 auto pref_b = r.first + len;
71 auto pref_e = r.second;
73 while (pref_b != pref_e && b != e) {
80 if (pref_b != pref_e) {
84 if (b == e && nd_it.m_p_nd->m_type == 1) {
88 if (b != e && nd_it.m_p_nd->m_type == 1 && (*nd_it)->second) {
92 const size_type num_children = nd_it.num_children();
93 len = pref_b - r.first;
94 for (size_type i = 0; i < num_children; ++i) {
95 if (search_recursive(nd_it.get_child(i), end_nd_it, b, e, len)) {
104 search_wildcardly(
typename access_traits::const_iterator b
105 ,
typename access_traits::const_iterator e) {
106 Node_Itr nd_it = this->node_begin();
107 Node_Itr end_nd_it = this->node_end();
108 return search_recursive(nd_it, end_nd_it, b, e, 0);
110 void operator()(node_iterator , node_const_iterator )
const{}
114 :
private __gnu_pbds::trie<std::string, bool, stringAccessTraits, __gnu_pbds::pat_trie_tag,
115 string_wildcard_trie_search, std::allocator<char>> {
116 using Base = __gnu_pbds::trie<std::string, bool,
stringAccessTraits, __gnu_pbds::pat_trie_tag,
122 void add(std::string
const& s) {
123 if (s[s.size() - 1] ==
'*') {
124 (*this)[s.substr(0, s.size() - 1)] =
true;
130 auto erase(std::string
const& s) {
131 if (s[s.size() - 1] ==
'*') {
132 return Base::erase(s.substr(0, s.size() - 1));
134 return Base::erase(s);
138 bool check(
char const*b,
size_t len)
const {
139 return const_cast<StringTrieSet*
>(
this)->search_wildcardly(b, b + len);
142 bool check(std::pair<char const*, char const*>
const& str)
const {
143 return const_cast<StringTrieSet*
>(
this)->search_wildcardly(str.first, str.second);
Definition: StringTrieSet.hpp:51
Definition: StringTrieSet.hpp:15
Definition: StringTrieSet.hpp:113
Definition: TypedString.hpp:74
static size_type e_pos(e_type e)
Maps an element to a position.
Definition: StringTrieSet.hpp:42
static const_iterator begin(key_const_reference ck)
Definition: StringTrieSet.hpp:33
static const_iterator end(key_const_reference ck)
Definition: StringTrieSet.hpp:38
Definition: Client.hpp:11