//#include "pch.h"
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
short cer;
char w[100];

class  TrieClass
{
public:
	TrieClass *next[21];
	int wordEndsHere;
	int wordsContains;
};

void add_trie(TrieClass *trieNode, char *word)
{
	trieNode->wordsContains++;
	if (*word == 0)
	{
		trieNode->wordEndsHere++;
		return;
	}
	int nextIndex = *word - 'a';
	if (trieNode->next[nextIndex] == NULL)
	{
		trieNode->next[nextIndex] = (TrieClass*)calloc(1, sizeof(TrieClass));
	}
	add_trie(trieNode->next[nextIndex], word + 1);
}

void remove_trie(TrieClass *trieNode, char *word)
{
	trieNode->wordsContains--;
	if (*word == 0)
	{
		trieNode->wordEndsHere--;
		return;
	}
	int nextIndex = *word - 'a';
	remove_trie(trieNode->next[nextIndex], word + 1);
	if (trieNode->next[nextIndex]->wordsContains == 0)
	{
		free(trieNode->next[nextIndex]);
		trieNode->next[nextIndex] = NULL;
	}
}

int aparitii_trie(TrieClass* trieNode, char* word)
{
	if (*word == 0)
	{
		return trieNode->wordEndsHere;
	}
	int nextIndex = *word - 'a';
	if (trieNode->next[nextIndex] == NULL)
	{
		return 0;
	}
	return aparitii_trie(trieNode->next[nextIndex], word + 1);
}

int longest_common_prefix(TrieClass* trieNode, char* word)
{
	if (*word == 0)
	{
		return 0;
	}
	int nextIndex = *word - 'a';
	if (trieNode->next[nextIndex] == NULL)
	{
		return 0;
	}
	return 1 + longest_common_prefix(trieNode->next[nextIndex], word + 1);
}



int main()
{
	FILE *f = fopen("trie.in", "r");
	FILE *o = fopen("trie.out", "w");
	TrieClass *trie = (TrieClass*)calloc(1, sizeof(TrieClass));

	/*
	0 w - adauga o aparitie a cuvantului w in lista
	1 w - sterge o aparitie a cuvantului w din lista
	2 w - tipareste numarul de aparitii ale cuvantului w in lista
	3 w - tipareste lungimea celui mai lung prefix comun al lui w cu oricare cuvant din lista
	*/


	while (fscanf(f, "%d  %s", &cer, &w) == 2) //fscanf returneaza nr de variabile citite cu succes
	{
		switch (cer)
		{
		case 0:
			add_trie(trie, w);
			break;
		case 1:
			remove_trie(trie, w);
			break;
		case 2:
			//cout << aparitii_trie(trie, w) << "\n";
			fprintf(o, "%d\n", aparitii_trie(trie, w));
			break;
		case 3:
			//cout << longest_common_prefix(trie, w) << "\n";
			fprintf(o, "%d\n", longest_common_prefix(trie, w));
			break;
		}
	}

}