#include <fstream>
#include <string>
#include <list>

using namespace std;

ifstream f("trie.in");
ofstream g("trie.out");

struct Node {
	list<Node*> children;
	char ch;
	int wordsEndingHere;
};

class Trie {
private:
	Node* root;
	void _deleteWord(string&, string::iterator, Node*);
	list<Node*>::iterator _findChild(char, Node*);

public:
	Trie() {
		root = new Node{ list<Node*>(), ' ', 0 };
	}

	void insertWord(const string&);
	void deleteWord(string&);
	int showNumOcc(const string&);
	int longestCommonPref(const string&);
};

void Trie::_deleteWord(string &word, string::iterator crtChar, Node* crtNode) {
	if (crtChar == word.end()) {
		crtNode->wordsEndingHere -= 1;
		return;
	}
	auto it = _findChild((*crtChar), crtNode);
	_deleteWord(word, crtChar + 1, *it);
	if ((*it)->wordsEndingHere == 0 && (*it)->children.size() == 0) {
		Node* toDel = *it;
		crtNode->children.erase(it);
		delete (toDel);
	}
}

list<Node*>::iterator Trie::_findChild(char ch, Node* node) {
	list<Node*>::iterator it = node->children.begin();
	for (; it != node->children.end(); ++it) {
		if ((*it)->ch == ch)
			break;
	}
	
	return it;
}

void Trie::insertWord(const string &word) {
	Node* crtNode = root;
	for (auto ch : word) {
		auto it = _findChild(ch, crtNode);
		if (it != crtNode->children.end())
			crtNode = (*it);
		else {
			Node* newNode = new Node{ list<Node*>(), ch, 0 };
			crtNode->children.push_back(newNode);
			crtNode = newNode;
		}
	}
	crtNode->wordsEndingHere += 1;
}

void Trie::deleteWord(string &word) {
	_deleteWord(word, word.begin(), root);
}

int Trie::showNumOcc(const string &word) {
	Node* crtNode = root;
	list<Node*>::iterator it;
	for (auto ch : word) {
		it = _findChild(ch, crtNode);
		if (it == crtNode->children.end())
			return 0;
		crtNode = (*it);
	}
	
	return (*it)->wordsEndingHere;
}

int Trie::longestCommonPref(const string &word) {
	Node* crtNode = root;
	int prefixLen = 0;
	for (char ch : word) {
		auto child = _findChild(ch, crtNode);
		if (child == crtNode->children.end())
			break;

		prefixLen++;
		crtNode = *child;
	}

	return prefixLen;
}

int main()
{
	int cmd;
	string word;
	Trie* trie = new Trie;
	while (f >> cmd) {
		f >> word;
		switch (cmd) {
		case 0:
			trie->insertWord(word);
			break;
		case 1:
			trie->deleteWord(word);
			break;
		case 2:
			g << trie->showNumOcc(word) << '\n';
			break;
		case 3:
			g << trie->longestCommonPref(word) << '\n';
			break;
		}
	}
}