#include <fstream>
#include <algorithm>
#include <unordered_map>
#include <memory>
#include <string>
#include <sstream>

struct TrieNode
{
	TrieNode(char character, const std::string& wordBefore) :
		m_Character(character),
		m_FullString(wordBefore + character),
		m_CountIndex(0)
	{}

	std::string m_FullString;
	char m_Character;
	int m_CountIndex;
	std::unordered_map<char, TrieNode*> m_Children;
};

TrieNode* trieRoot = new TrieNode(0, "");

void InsertWord(const std::string& word)
{
	int charIndex = 0;
	TrieNode* node = trieRoot;
	while (charIndex < word.length())
	{
		auto currentChar = word[charIndex];
		auto existingChild = node->m_Children.find(currentChar);
		if (existingChild != node->m_Children.end())
		{
			charIndex++;
			node = existingChild->second;
		}
		else
		{
			break;
		}
	}
	while (charIndex < word.length())
	{
		auto currentChar = word[charIndex];
		node->m_Children.emplace(currentChar, new TrieNode(currentChar, node->m_FullString));
		node = node->m_Children[currentChar];
		charIndex++;
	}
	node->m_CountIndex++;
}

TrieNode* FindEndOfWordNode(const std::string& word)
{
	int charIndex = 0;
	TrieNode* node = trieRoot;
	while (charIndex < word.length())
	{
		auto currentChar = word[charIndex];
		auto existingChild = node->m_Children.find(currentChar);
		charIndex++;
		node = existingChild->second;
	}
	return node;
}

void DecrementWordCount(const std::string& word)
{
	auto node = FindEndOfWordNode(word);
	node->m_CountIndex--;
}

int GetWordCount(const std::string& word)
{
	auto node = FindEndOfWordNode(word);
	return node->m_CountIndex;
}

bool AnyChildContainsValidNodes(TrieNode* node)
{
	if (node->m_CountIndex > 0)
	{
		return true;
	}
	for (auto kvPair : node->m_Children)
	{
		if (AnyChildContainsValidNodes(kvPair.second))
		{
			return true;
		}
	}
	return false;
}

int GetLongestPrefixLength(const std::string& word)
{
	int charIndex = 0;
	TrieNode* node = trieRoot;
	int length = 0;
	int lengthMilestone = 0;
	while (charIndex < word.length())
	{
		if (AnyChildContainsValidNodes(node))
		{
			lengthMilestone = length;
		}
		auto currentChar = word[charIndex];
		auto existingChild = node->m_Children.find(currentChar);
		if (existingChild != node->m_Children.end())
		{
			node = existingChild->second;
			charIndex++;
			length++;
		}
		else
		{
			return lengthMilestone;
		}
	}
	return lengthMilestone;
}

void ExecInstruction(char instruction, const std::string& word, std::ostream& out)
{
	switch (instruction)
	{
	case('0') : InsertWord(word); break;
	case('1') : DecrementWordCount(word); break;
	case('2') : out << GetWordCount(word) << "\n"; break;
	case('3') : out << GetLongestPrefixLength(word) << "\n"; break;
	default:break;
	}
}

int main()
{
	std::ifstream inFile("trie.in");
	std::ofstream outFile("trie.out");
	std::string line;
	while (std::getline(inFile, line))
	{
		auto word = line.substr(2, line.length());
		ExecInstruction(line[0], word, outFile);
	}
	outFile.close();
	inFile.close();
}