#include <fstream>
#include <iostream>
#include <string>
using namespace std;
ifstream f("trie.in");
ofstream g("trie.out");
const int SIGMA = 26;
struct Trie {
int words; // numarul de aparitii al cuvantului din nod
int fii; // numarul de fii al nodului, descendentii vor avea cuvantul respectiv ca prefix
Trie *son[SIGMA];
Trie() {
words = fii = 0;
for (int i = 0; i < 26; i++)
son[i] = NULL;
}
};
Trie *root = new Trie;
string word;
void Insert (Trie *node, int pos) {
if (word[pos] == '\0') {
node->words++;
return;
}
int ch = word[pos] - 'a';
if (node->son[ch] == NULL) {
node->son[ch] = new Trie;
node->fii++;
}
Insert (node->son[ch], pos + 1);
}
int Delete (Trie *node, int pos) {
int ch = word[pos] - 'a';
if (word[pos] == '\0') // am ajuns in nodul care tine tot cuvantul
node->words--;
else if (Delete (node->son[ch], pos + 1) == 1) {
node->son[ch] = NULL;
node->fii--;
}
if (node->words == 0 && node->fii == 0 && node != root) {
delete node;
return 1;
}
return 0;
}
int query (Trie *node, int pos) {
int ch = word[pos] - 'a';
if (word[pos] == '\0')
return node->words;
if (node->son[ch] == NULL)
return 0;
return query (node->son[ch], pos + 1);
}
int prefix (Trie *node, int pos, int ret) {
int ch = word[pos] - 'a';
if (word[pos] == '\0' || node->son[ch] == NULL)
return ret;
return prefix (node->son[ch], pos + 1, ret + 1);
}
int main() {
int op;
while (f >> op >> word) {
switch (op) {
case 0 : Insert (root, 0); break;
case 1 : Delete (root, 0); break;
case 2 : g << query (root, 0) << '\n'; break;
case 3 : g << prefix (root, 0, 0) << '\n'; break;
}
word.clear();
}
f.close();
g.close();
return 0;
}