#include <stdio.h>
#include <stdint.h>
#include <string.h>

struct TrieNode;
TrieNode* tnalloc();

class TrieNode {
  TrieNode* kids[2];
  bool  hasWord;
  int id;

public:
  void insert (const void* buf, size_t n) {
    const uint8_t* bytes = (const uint8_t*)buf;
    TrieNode* p = this;
    while (n--) {
      for (uint8_t m = 0x80; m; m >>= 1) {
        const int i = bytes[n] & m ? 1 : 0;
        if (!p->kids[i]) p->kids[i] = tnalloc();
        p = p->kids[i];
        //printf("insert: %d\n", p->id);
      }
    }
    p->hasWord = true;
    //printf("%d has word\n", p->id);
  }

  bool find (const void* buf, size_t n) {
    const uint8_t* bytes = (const uint8_t*)buf;
    TrieNode* p = this;
    while (n--) {
      for (uint8_t m = 0x80; m; m >>= 1) {
        const int i = bytes[n] & m ? 1 : 0;
        if (!p->kids[i]) goto done;
        p = p->kids[i];
      }
    }
    done:
    //printf("find: %d\n", p->id);
    return p->hasWord;
  }

  friend TrieNode* tnalloc();
};

TrieNode* tnalloc () {
  static TrieNode all[1000 * 1000];
  static int n = 0;
  TrieNode* p = all + n++;
  p->kids[0] = p->kids[1] = 0; p->hasWord = false;
  p->id = n - 1;
  return p;
}

void insert(TrieNode* p, const char* s) {
  p->insert(s, strlen(s)); // 防"ab", 1
  printf("%s in trie\n", s);
}

int main (int argc, char** argv) {
  if (argc != 2) return 0;
  TrieNode* r = tnalloc();
  insert(r, "ab"); insert(r, "abc"); insert(r, "abd");
  printf("%d\n", r->find(argv[1], strlen(argv[1])));
  return 0;
}