#include <iostream>
#include <fstream>
#include <string.h>

#define MAX_CHILDREN 26
#define MAX_WORD 100

struct TrieNode
{
public:
	unsigned short m_EndNodeCount;
	TrieNode *m_Children[MAX_CHILDREN];

public:
	TrieNode();
	~TrieNode();
};

TrieNode::TrieNode()
{
	m_EndNodeCount = 0;

	unsigned short i;

	for (i = 0; i < MAX_CHILDREN; i++)
	{
		m_Children[i] = nullptr;
	}
}

TrieNode::~TrieNode()
{

}

void insertWord(TrieNode *root, const char *word)
{
	unsigned char word_length = strlen(word);

	unsigned char i;

	TrieNode *current_node = root;

	for (i = 0; i < word_length; i++)
	{
		unsigned char index = word[i] - 'a';

		if (current_node->m_Children[index] == nullptr)
		{
			current_node->m_Children[index] = new TrieNode;
		}

		current_node = current_node->m_Children[index];
	}

	current_node->m_EndNodeCount++;
}

void deleteWord(TrieNode *root, const char *word)
{
    if (root == nullptr)
	{
		return;
	}

	unsigned char word_length = strlen(word);

	unsigned char i;

	TrieNode *current_node = root;

	for (i = 0; i < word_length; i++)
	{
		unsigned char index = word[i] - 'a';

		if (!current_node->m_Children[index])
		{
			return;
		}

		current_node = current_node->m_Children[index];
	}

	current_node->m_EndNodeCount--;
}

unsigned short getWordCount(TrieNode *root, const char *word)
{
	if (root == nullptr)
	{
		return 0;
	}

	TrieNode *current_node = root;
	unsigned char word_length = strlen(word);
	unsigned char i;

	for (i = 0; i < word_length; i++)
	{
		unsigned char index = word[i] - 'a';

		if (!current_node->m_Children[index])
		{
			return 0;
		}

		current_node = current_node->m_Children[index];
	}

	return current_node->m_EndNodeCount;
}

unsigned short getMaxPrefix(TrieNode *root, const char *word)
{
    if (root == nullptr)
	{
		return 0;
	}

	TrieNode *current_node = root;
	unsigned char word_length = strlen(word);
	unsigned char i;
    unsigned short counter = 0;

	for (i = 0; i < word_length; i++)
	{
		unsigned char index = word[i] - 'a';

		if (!current_node->m_Children[index])
		{
			return counter;
		}
        else
        {
            counter++;
            current_node = current_node->m_Children[index];
        }
	}

	return counter;
}

int main()
{
    TrieNode *root = new TrieNode;

    FILE *ifile = fopen("trie.in","r");
    FILE *ofile = fopen("trie.out","w");

    char op;
    char word[21];

    while(!feof(ifile))
    {
        op = fgetc(ifile) - '0';
        fgetc(ifile);

        fscanf(ifile, "%s", word);
        fgetc(ifile);


        switch (op)
        {
        case 0:
            insertWord(root, word);
            break;

        case 1:
            deleteWord(root, word);
            break;

        case 2:
            fprintf(ofile, "%d", getWordCount(root, word));
            fputc('\n', ofile);
            break;

        case 3:
            fprintf(ofile, "%d", getMaxPrefix(root, word));
            fputc('\n', ofile);
            break;
        }
    }

    fclose(ifile);
    fclose(ofile);

    return 0;
}