fork download
copy 
  1. /*
  2.   Copyright 2012 Marek "p2004a" Rusinowski
  3.   Trie tree
  4. */
  5. #include <cstdio>
  6.  
  7. class Trie {
  8.   Trie *son[26];
  9.   char num;
  10.   bool end;
  11.  
  12.  public:
  13.   Trie() : num(0), end(false) {
  14.     for (int i = 0; i < 26; ++i) {
  15.       son[i] = NULL;
  16.     }
  17.   }
  18.  
  19.   ~Trie() {
  20.     for (int i = 0; i < 26; ++i) {
  21.       if (son[i] != NULL) delete son[i];
  22.     }
  23.   }
  24.  
  25.   #define x son[*c - 'a']
  26.  
  27.   void add(char *c) {
  28.     if (*c == '\0') {
  29.       end = true;
  30.       return;
  31.     }
  32.     if (x == NULL) {
  33.       x = new Trie;
  34.       ++num;
  35.     }
  36.     x->add(c + 1);
  37.   }
  38.  
  39.   bool query(char *c) {
  40.     if (*c == '\0') return end;
  41.     return x != NULL && x->query(c + 1);
  42.   }
  43.  
  44.   bool erase(char *c) {
  45.     if (*c == '\0') {
  46.       bool tmp = end;
  47.       end = false;
  48.       return tmp;
  49.     }
  50.     if (x != NULL && x->erase(c + 1) && x->num == 0 && x->end == false) {
  51.       delete x;
  52.       x = NULL;
  53.       --num;
  54.       return true;
  55.     }
  56.     return false;
  57.   }
  58.  
  59.   #undef x
  60. };
  61.  
  62. char str[1000000];
  63.  
  64. int main() {
  65.   int n;
  66.   char c;
  67.   scanf("%d\n", &n);
  68.   Trie tree;
  69.   while (n--) {
  70.     scanf("%c %s\n", &c, str);
  71.     switch (c) {
  72.       case 'a':
  73.         tree.add(str);
  74.         printf("add\n");
  75.         break;
  76.       case 'q':
  77.         printf(tree.query(str) ? "true\n" : "false\n");
  78.         break;
  79.       case 'e':
  80.         tree.erase(str);
  81.         break;
  82.     }
  83.   }
  84.   return 0;
  85. }
  86.  
Success #stdin #stdout 0.01s 3796KB
comments (?)
stdin
copy 
8
a abba
a banan
a ababa
q abb
q abba
q ban
e abba
q abba
stdout
copy 
add
add
add
false
true
false
false
https://ideone.com/gudmy
Trie tree
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!