Code-book/trie.cpp at master · saisumit/Code-book · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#define DIST 100

struct node
{
   node * ar[ DIST ]  ;
   int  cnt = 0 ;
   bool End = false ;
   node() { FOR( i , DIST ) ar[i] = NULL ;  }
};

void trie_insert( node* root , string& s )
 {
    node* hd  =  root ;
    for( int i  = 0 ; i < s.length() ; i ++ )
      {
      	  int idx = s[i] - 'A' ;
          node** ar = hd->ar ;
          if( ar[idx] == NULL )
           {
              node* tp = new node() ;
              ar[idx] = tp ;
              ar[idx]->cnt = 1 ;
              hd = tp ;
           }
          else
           {
           	    (ar[idx]->cnt ) ++ ;
           	     hd  =  ar[idx] ;
           }

      }

     hd->End = true ;

 }

void Print_Trie( node* hd ,  string pr )
 {
   if( hd->End )cout<<pr<<endl;
   node** ar = hd->ar  ;

   FOR( i , DIST )
      if( ar[i] != NULL )
        {
          char u = i + 'A' ;
          Print_Trie( ar[i] , pr + u ) ;
        }
 }


node* Trie_Match( node* root ,  string& s  , int L , int R )
 {
    node* hd = root ;

    for( int i = L ; i <= R ; i ++ )
     {
        int idx = s[i] - 'A' ;
        node** ar = hd->ar ;
        if( ar[idx] == NULL ){ return false ; }
        else hd = ar[idx] ;
     }

   return  hd ;

 }


void trie_remove( node& root , string& s )
 {
     node* hd = root ;
     for( int i = 0 ; i < s.length() ; i ++ )
     	{
          int idx = s[i] - 'A' ;
          node** ar = hd->ar ;
          if( ar[idx] != NULL )
          	 {
          	 	ar[idx]->cnt -- ;
          	 	hd = ar[idx] ;
          	 	if( ar[idx]-> cnt == 0 )
          	      {
          	      	ar[idx] = NULL ;
          	      	break ;
          	      }
          	 }

     	}

 }