#include <iostream>
#include <fstream>
#include <string>
#include <unordered_map>
using namespace std;
class Constants {
public:
static const int ALPHABET_SIZE;
};
const int Constants::ALPHABET_SIZE = 30;
class Trie;
class Node {
private:
int counter;
short words;
unordered_map<char, Node*> v;
public:
Node();
~Node();
friend class Trie;
};
Node::Node() {
words = 0;
counter = 0;
}
Node::~Node() {
for (auto& it : v) {
delete it.second;
v.erase(it.first);
}
}
class Trie {
private:
Node* root;
public:
Trie();
~Trie();
void add(string s);
void remove(string s);
short search(string s);
short prefix(string s);
/* data */
};
Trie::Trie() {
root = new Node();
}
Trie::~Trie() {
delete root;
}
void Trie::add(string s) {
auto node = root;
for (auto it : s) {
if (node->v.find(it) == node->v.end())
node->v[it] = new Node();
node = node->v[it];
node->counter++;
}
node->words++;
}
void Trie::remove(string s) {
auto node = root;
for (auto it : s) {
if ( node->v.find(it) == node->v.end())
return;
if (--node->v[it]->counter == 0) {
delete node->v[it];
node->v.erase(it);
return;
}
node = node->v[it];
}
node->words--;
}
short Trie::search(string s) {
auto node = root;
for (auto it : s) {
if ( node->v.find(it) == node->v.end())
return 0;
node = node->v[it];
}
return node->words;
}
short Trie::prefix(string s) {
auto node = root;
short result = 0;
short app = search(s);
for (auto it : s) {
if ( node->v.find(it) == node->v.end())
return result;
if (node->v[it]->counter == app)
return result;
result++;
node = node->v[it];
}
return result;
}
int main(int argc, char const *argv[]) {
Trie problem;
ifstream in("trie.in");
ofstream out("trie.out");
int n;
string s;
while (in>>n) {
in>>s;
switch (n) {
// case 0 :
// problem.add(s);
// break;
// case 1 :
// problem.remove(s);
// break;
// case 2 :
// out<<problem.search(s)<<"\n";
// break;
// case 3 :
// out<<problem.prefix(s)<<"\n";
// break;
}
}
return 0;
}