#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "template/template.hpp"
#include "string/trie.hpp"
int main () {
{
Trie <> trie ;
assert ( trie . empty ());
assert ( trie . add ( "" , 0 ) == trie . root_node ());
int a = trie . add ( "a" , 1 );
assert ( a == trie . find_node ( "a" ));
int ab = trie . add ( "ab" , 2 );
assert ( ab == trie . find_node ( "ab" ));
int abc = trie . add ( "abc" , 3 );
assert ( abc == trie . find_node ( "abc" ));
int abd = trie . add ( "abd" , 4 );
assert ( abd == trie . find_node ( "abd" ));
int ab2 = trie . add ( "ab" , 5 );
assert ( ab2 == trie . find_node ( "ab" ));
int b = trie . add ( "b" , 6 );
assert ( b == trie . find_node ( "b" ));
assert ( trie . size () == 7 );
assert ( trie . count () == 7 );
assert ( ! trie . empty ());
assert ( trie . count ( "" ) == 1 );
assert ( trie . count ( "a" ) == 1 );
assert ( trie . count ( "ab" ) == 2 );
assert ( trie . count ( "ac" ) == 0 );
assert ( trie . contains ( "abc" ));
assert ( ! trie . contains ( "ac" ));
assert ( trie . count_prefix ( "" ) == 7 );
assert ( trie . count_prefix ( "a" ) == 5 );
assert ( trie . count_prefix ( "ab" ) == 4 );
assert ( trie . count_prefix ( "abc" ) == 1 );
assert ( trie . count_prefix ( "ac" ) == 0 );
assert ( trie . find_ids ( "ab" ) == vector < int > ({ 2 , 5 }));
assert ( trie . find_ids ( "ac" ). empty ());
assert ( trie . prefix_match ( "abcd" ) == vector < int > ({ 0 , 1 , 2 , 5 , 3 }));
assert ( trie . enumerate_prefix ( "a" ) == vector < int > ({ 1 , 2 , 5 , 3 , 4 }));
assert ( trie . enumerate_prefix ( "ab" ) == vector < int > ({ 2 , 5 , 3 , 4 }));
assert ( trie . longest_prefix ( "abcd" ) == 3 );
assert ( trie . longest_prefix ( "ac" ) == 1 );
assert ( trie . longest_prefix ( "c" ) == 0 );
int v = trie . find_node ( "abd" );
assert ( v != - 1 );
assert ( trie . restore ( v ) == "abd" );
assert ( trie . next_node ( trie . find_node ( "ab" ), 'd' ) == v );
assert ( trie . next_node ( trie . find_node ( "ab" ), 'e' ) == - 1 );
assert ( ! trie . insert ( "ab" , 100 ));
assert ( trie . erase ( "ab" , 5 ));
assert ( trie . find_ids ( "ab" ) == vector < int > ({ 2 }));
assert ( trie . count_prefix ( "a" ) == 4 );
assert ( trie . size () == 6 );
assert ( ! trie . erase ( "ab" , 5 ));
assert ( trie . erase ( "ab" ));
assert ( ! trie . contains ( "ab" ));
assert ( trie . count_prefix ( "a" ) == 3 );
assert ( trie . size () == 5 );
assert ( trie . insert ( "ab" , 7 ));
assert ( trie . find_ids ( "ab" ) == vector < int > ({ 7 }));
trie . clear ();
assert ( trie . empty ());
assert ( trie . node_size () == 1 );
assert ( trie . find_node ( "" ) == trie . root_node ());
}
{
Trie < 10 , '0' > trie ;
trie . add ( "012" , 10 );
trie . add ( "01" , 11 );
assert ( trie . count_prefix ( "0" ) == 2 );
assert ( trie . longest_prefix ( "0123" ) == 3 );
assert ( trie . prefix_match ( "0123" ) == vector < int > ({ 11 , 10 }));
}
int a , b ;
in ( a , b );
out ( a + b );
} #line 1 "verify/string/UNIT_trie.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "template/template.hpp"
#include <bits/stdc++.h>
using namespace std ;
#line 2 "template/macro.hpp"
#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(b) - 1; i >= (a); i--)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin())
#define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin())
#define YN(b) cout << ((b) ? "YES" : "NO") << "\n";
#define Yn(b) cout << ((b) ? "Yes" : "No") << "\n";
#define yn(b) cout << ((b) ? "yes" : "no") << "\n";
#line 6 "template/template.hpp"
#line 2 "template/util.hpp"
using uint = unsigned int ;
using ll = long long int ;
using ull = unsigned long long ;
using i128 = __int128_t ;
using u128 = __uint128_t ;
template < class T >
using priority_queue_asc = priority_queue < T , vector < T > , greater < T >> ;
template < class T , class S = T >
S SUM ( const vector < T >& a ) {
return accumulate ( ALL ( a ), S ( 0 ));
}
template < class T1 , class T2 >
inline bool chmin ( T1 & a , T2 b ) {
if ( a > b ) {
a = b ;
return true ;
}
return false ;
}
template < class T1 , class T2 >
inline bool chmax ( T1 & a , T2 b ) {
if ( a < b ) {
a = b ;
return true ;
}
return false ;
}
template < class T1 , class T2 >
inline bool chmin_opt ( optional < T1 >& a , T2 b ) {
if ( ! a || a > b ) {
a = b ;
return true ;
}
return false ;
}
template < class T1 , class T2 >
inline bool chmax_opt ( optional < T1 >& a , T2 b ) {
if ( ! a || a < b ) {
a = b ;
return true ;
}
return false ;
}
template < class T >
int popcnt ( T x ) {
return __builtin_popcountll ( x );
}
template < class T >
int topbit ( T x ) {
return ( x == 0 ? - 1 : 63 - __builtin_clzll ( x ));
}
template < class T >
int lowbit ( T x ) {
return ( x == 0 ? - 1 : __builtin_ctzll ( x ));
}
#line 8 "template/template.hpp"
#line 2 "template/inout.hpp"
struct Fast {
Fast () {
cin . tie ( nullptr );
ios_base :: sync_with_stdio ( false );
cout << fixed << setprecision ( 15 );
}
} fast ;
ostream & operator << ( ostream & os , __uint128_t x ) {
char buf [ 40 ];
size_t k = 0 ;
while ( x > 0 ) buf [ k ++ ] = ( char )( x % 10 + '0' ), x /= 10 ;
if ( k == 0 ) buf [ k ++ ] = '0' ;
while ( k ) os << buf [ -- k ];
return os ;
}
ostream & operator << ( ostream & os , __int128_t x ) {
return x < 0 ? ( os << '-' << ( __uint128_t )( - x )) : ( os << ( __uint128_t ) x );
}
template < class T , size_t N >
ostream & operator << ( ostream & os , const array < T , N >& a );
template < class T1 , class T2 >
istream & operator >> ( istream & is , pair < T1 , T2 >& p ) {
return is >> p . first >> p . second ;
}
template < class T1 , class T2 >
ostream & operator << ( ostream & os , const pair < T1 , T2 >& p ) {
return os << p . first << " " << p . second ;
}
template < class T >
istream & operator >> ( istream & is , vector < T >& a ) {
for ( auto & v : a ) is >> v ;
return is ;
}
template < class T >
ostream & operator << ( ostream & os , const vector < T >& a ) {
for ( auto it = a . begin (); it != a . end ();) {
os << * it ;
if ( ++ it != a . end ()) os << " " ;
}
return os ;
}
template < class T , size_t N >
ostream & operator << ( ostream & os , const array < T , N >& a ) {
for ( auto it = a . begin (); it != a . end ();) {
os << * it ;
if ( ++ it != a . end ()) os << " " ;
}
return os ;
}
template < class T >
ostream & operator << ( ostream & os , const set < T >& st ) {
os << "{" ;
for ( auto it = st . begin (); it != st . end ();) {
os << * it ;
if ( ++ it != st . end ()) os << "," ;
}
os << "}" ;
return os ;
}
template < class T1 , class T2 >
ostream & operator << ( ostream & os , const map < T1 , T2 >& mp ) {
os << "{" ;
for ( auto it = mp . begin (); it != mp . end ();) {
os << it -> first << ":" << it -> second ;
if ( ++ it != mp . end ()) os << "," ;
}
os << "}" ;
return os ;
}
void in () {}
template < typename T , class ... U >
void in ( T & t , U & ... u ) {
cin >> t ;
in ( u ...);
}
template < class ... T >
void in_zip ( int n , T & ... t ) {
assert ( n >= 0 && (( size ( t ) >= static_cast < size_t > ( n )) && ...));
for ( int i = 0 ; i < n ; i ++ ) in ( t [ i ]...);
}
void out () { cout << " \n " ; }
template < typename T , class ... U , char sep = ' ' >
void out ( const T & t , const U & ... u ) {
cout << t ;
if ( sizeof ...( u )) cout << sep ;
out ( u ...);
}
template < class T , class U >
void out_opt ( const optional < T >& opt , const U & fallback , ostream & os = cout ) {
if ( opt . has_value ())
os << opt . value ();
else
os << fallback ;
os << " \n " ;
}
template < class T , class U >
void out_opt ( const vector < optional < T >>& vec , const U & fallback , ostream & os = cout ) {
for ( auto it = vec . begin (); it != vec . end ();) {
if (( * it ). has_value ())
os << ( * it ). value ();
else
os << fallback ;
if ( ++ it != vec . end ()) os << " " ;
}
os << " \n " ;
}
namespace IO {
template < class T , class ... U >
T read ( U && ... u ) {
T t = T ( forward < U > ( u )...);
in ( t );
return t ;
}
namespace Graph {
vector < vector < int >> unweighted ( int n , int m , bool directed = false , int offset = 1 ) {
vector < vector < int >> g ( n );
for ( int i = 0 ; i < m ; i ++ ) {
int u , v ;
cin >> u >> v ;
u -= offset , v -= offset ;
g [ u ]. push_back ( v );
if ( ! directed ) g [ v ]. push_back ( u );
}
return g ;
}
template < class T >
vector < vector < pair < int , T >>> weighted ( int n , int m , bool directed = false , int offset = 1 ) {
vector < vector < pair < int , T >>> g ( n );
for ( int i = 0 ; i < m ; i ++ ) {
int u , v ;
T w ;
cin >> u >> v >> w ;
u -= offset , v -= offset ;
g [ u ]. push_back ({ v , w });
if ( ! directed ) g [ v ]. push_back ({ u , w });
}
return g ;
}
} // namespace Graph
namespace Tree {
vector < vector < int >> unweighted ( int n , bool directed = false , int offset = 1 ) {
return Graph :: unweighted ( n , n - 1 , directed , offset );
}
template < class T >
vector < vector < pair < int , T >>> weighted ( int n , bool directed = false , int offset = 1 ) {
return Graph :: weighted < T > ( n , n - 1 , directed , offset );
}
vector < vector < int >> rooted ( int n , bool to_root = true , bool to_leaf = true , int offset = 1 ) {
vector < vector < int >> g ( n );
for ( int i = 1 ; i < n ; i ++ ) {
int p ;
cin >> p ;
p -= offset ;
if ( to_root ) g [ i ]. push_back ( p );
if ( to_leaf ) g [ p ]. push_back ( i );
}
return g ;
}
} // namespace Tree
} // namespace IO
#line 10 "template/template.hpp"
#line 2 "template/debug.hpp"
#ifdef LOCAL
#define debug 1
#define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__)
#else
#define debug 0
#define show(...) true
#endif
template < class T >
void _show ( int , T ) {
cerr << '\n' ;
}
template < class T1 , class T2 , class ... T3 >
void _show ( int i , const T1 & a , const T2 & b , const T3 & ... c ) {
for (; a [ i ] != ',' && a [ i ] != '\0' ; i ++ ) cerr << a [ i ];
cerr << ":" << b << " " ;
_show ( i + 1 , a , c ...);
}
#line 2 "string/trie.hpp"
template < int char_size = 26 , char char_start = 'a' >
struct Trie {
struct Node {
int prev , count , c ;
int next [ char_size ];
vector < int > ids ;
Node ( int prev , int c ) : prev ( prev ), count ( 0 ), c ( c ) {
memset ( next , - 1 , sizeof ( next ));
}
};
Trie () : root ( make_node ()) {}
int add ( const string & str , int id = - 1 ) {
if ( id == - 1 ) id = size ();
int x = root ;
nodes [ x ]. count ++ ;
for ( auto c : str ) {
x = get_child ( x , char_index ( c ));
nodes [ x ]. count ++ ;
}
nodes [ x ]. ids . emplace_back ( id );
return x ;
}
bool insert ( const string & str , int id = - 1 ) {
if ( contains ( str )) return false ;
add ( str , id );
return true ;
}
bool erase ( const string & str ) {
int x = find_node ( str );
if ( x == - 1 || nodes [ x ]. ids . empty ()) return false ;
nodes [ x ]. ids . pop_back ();
subtract_path ( x );
return true ;
}
bool erase ( const string & str , int id ) {
int x = find_node ( str );
if ( x == - 1 ) return false ;
auto it = find ( nodes [ x ]. ids . begin (), nodes [ x ]. ids . end (), id );
if ( it == nodes [ x ]. ids . end ()) return false ;
nodes [ x ]. ids . erase ( it );
subtract_path ( x );
return true ;
}
int size () const { return nodes [ root ]. count ; }
int count () const { return size (); }
int node_size () const { return nodes . size (); }
bool empty () const { return size () == 0 ; }
int count ( const string & str ) const {
int x = find_node ( str );
return x == - 1 ? 0 : nodes [ x ]. ids . size ();
}
int count_prefix ( const string & str ) const {
int x = find_node ( str );
return x == - 1 ? 0 : nodes [ x ]. count ;
}
bool contains ( const string & str ) const { return count ( str ) > 0 ; }
vector < int > find_ids ( const string & str ) const {
int x = find_node ( str );
return x == - 1 ? vector < int > () : nodes [ x ]. ids ;
}
vector < int > prefix_match ( const string & str ) const {
vector < int > ret ;
int x = root ;
append ( ret , nodes [ x ]. ids );
for ( auto c : str ) {
x = next_node ( x , c );
if ( x == - 1 ) break ;
append ( ret , nodes [ x ]. ids );
}
return ret ;
}
vector < int > enumerate_prefix ( const string & str ) const {
vector < int > ret ;
int x = find_node ( str );
if ( x != - 1 ) dfs_ids ( x , ret );
return ret ;
}
int longest_prefix ( const string & str ) const {
int x = root , ret = nodes [ x ]. ids . empty () ? - 1 : 0 ;
for ( int i = 0 ; i < ( int ) str . size (); i ++ ) {
x = next_node ( x , str [ i ]);
if ( x == - 1 ) break ;
if ( ! nodes [ x ]. ids . empty ()) ret = i + 1 ;
}
return ret ;
}
int root_node () const { return root ; }
int find_node ( const string & str ) const {
int x = root ;
for ( auto c : str ) {
x = next_node ( x , c );
if ( x == - 1 ) return - 1 ;
}
return x ;
}
int next_node ( int index , char c ) const {
return index == - 1 ? - 1 : nodes [ index ]. next [ char_index ( c )];
}
const Node & node ( int index ) const { return nodes [ index ]; }
string restore ( int index ) const {
string ret ;
while ( index != root ) {
ret . push_back ( char_start + nodes [ index ]. c );
index = nodes [ index ]. prev ;
}
reverse ( ret . begin (), ret . end ());
return ret ;
}
void clear () {
nodes . clear ();
root = make_node ();
}
private:
vector < Node > nodes ;
int root ;
int make_node ( int prev = - 1 , int c = - 1 ) {
nodes . push_back ( Node ( prev , c ));
return nodes . size () - 1 ;
}
int get_child ( int index , int char_index ) {
if ( nodes [ index ]. next [ char_index ] == - 1 ) {
int child = make_node ( index , char_index );
nodes [ index ]. next [ char_index ] = child ;
}
return nodes [ index ]. next [ char_index ];
}
int char_index ( char c ) const {
int x = c - char_start ;
assert ( 0 <= x && x < char_size );
return x ;
}
void subtract_path ( int index ) {
while ( index != - 1 ) {
nodes [ index ]. count -- ;
index = nodes [ index ]. prev ;
}
}
void append ( vector < int >& a , const vector < int >& b ) const {
a . insert ( a . end (), b . begin (), b . end ());
}
void dfs_ids ( int index , vector < int >& ret ) const {
append ( ret , nodes [ index ]. ids );
for ( int c = 0 ; c < char_size ; c ++ )
if ( nodes [ index ]. next [ c ] != - 1 ) dfs_ids ( nodes [ index ]. next [ c ], ret );
}
};
/**
* @brief Trie
* @docs docs/string/trie.md
*/
#line 5 "verify/string/UNIT_trie.test.cpp"
int main () {
{
Trie <> trie ;
assert ( trie . empty ());
assert ( trie . add ( "" , 0 ) == trie . root_node ());
int a = trie . add ( "a" , 1 );
assert ( a == trie . find_node ( "a" ));
int ab = trie . add ( "ab" , 2 );
assert ( ab == trie . find_node ( "ab" ));
int abc = trie . add ( "abc" , 3 );
assert ( abc == trie . find_node ( "abc" ));
int abd = trie . add ( "abd" , 4 );
assert ( abd == trie . find_node ( "abd" ));
int ab2 = trie . add ( "ab" , 5 );
assert ( ab2 == trie . find_node ( "ab" ));
int b = trie . add ( "b" , 6 );
assert ( b == trie . find_node ( "b" ));
assert ( trie . size () == 7 );
assert ( trie . count () == 7 );
assert ( ! trie . empty ());
assert ( trie . count ( "" ) == 1 );
assert ( trie . count ( "a" ) == 1 );
assert ( trie . count ( "ab" ) == 2 );
assert ( trie . count ( "ac" ) == 0 );
assert ( trie . contains ( "abc" ));
assert ( ! trie . contains ( "ac" ));
assert ( trie . count_prefix ( "" ) == 7 );
assert ( trie . count_prefix ( "a" ) == 5 );
assert ( trie . count_prefix ( "ab" ) == 4 );
assert ( trie . count_prefix ( "abc" ) == 1 );
assert ( trie . count_prefix ( "ac" ) == 0 );
assert ( trie . find_ids ( "ab" ) == vector < int > ({ 2 , 5 }));
assert ( trie . find_ids ( "ac" ). empty ());
assert ( trie . prefix_match ( "abcd" ) == vector < int > ({ 0 , 1 , 2 , 5 , 3 }));
assert ( trie . enumerate_prefix ( "a" ) == vector < int > ({ 1 , 2 , 5 , 3 , 4 }));
assert ( trie . enumerate_prefix ( "ab" ) == vector < int > ({ 2 , 5 , 3 , 4 }));
assert ( trie . longest_prefix ( "abcd" ) == 3 );
assert ( trie . longest_prefix ( "ac" ) == 1 );
assert ( trie . longest_prefix ( "c" ) == 0 );
int v = trie . find_node ( "abd" );
assert ( v != - 1 );
assert ( trie . restore ( v ) == "abd" );
assert ( trie . next_node ( trie . find_node ( "ab" ), 'd' ) == v );
assert ( trie . next_node ( trie . find_node ( "ab" ), 'e' ) == - 1 );
assert ( ! trie . insert ( "ab" , 100 ));
assert ( trie . erase ( "ab" , 5 ));
assert ( trie . find_ids ( "ab" ) == vector < int > ({ 2 }));
assert ( trie . count_prefix ( "a" ) == 4 );
assert ( trie . size () == 6 );
assert ( ! trie . erase ( "ab" , 5 ));
assert ( trie . erase ( "ab" ));
assert ( ! trie . contains ( "ab" ));
assert ( trie . count_prefix ( "a" ) == 3 );
assert ( trie . size () == 5 );
assert ( trie . insert ( "ab" , 7 ));
assert ( trie . find_ids ( "ab" ) == vector < int > ({ 7 }));
trie . clear ();
assert ( trie . empty ());
assert ( trie . node_size () == 1 );
assert ( trie . find_node ( "" ) == trie . root_node ());
}
{
Trie < 10 , '0' > trie ;
trie . add ( "012" , 10 );
trie . add ( "01" , 11 );
assert ( trie . count_prefix ( "0" ) == 2 );
assert ( trie . longest_prefix ( "0123" ) == 3 );
assert ( trie . prefix_match ( "0123" ) == vector < int > ({ 11 , 10 }));
}
int a , b ;
in ( a , b );
out ( a + b );
} 
verify/string/UNIT_trie.test.cpp
template/debug.hpp