#include <fstream>
#include <cstring>
#define CH (*s-'a')
using namespace std;
char s[32];
struct Trie 
{
	int nr, nrfii;
	Trie *fiu[ 26 ];
	Trie() 
	{
		nr=nrfii=0;
		memset(fiu,0,sizeof(fiu));
	}
}*T;

void adauga(Trie *nod,char *s )//adauga un cuvant
{
	if(*s>'z' || *s<'a') 
	{
		nod->nr ++; return;
	}
	if(nod->fiu[CH]==0) 
	{
		nod->fiu[CH]=new Trie;
		nod->nrfii++;
	}
	adauga(nod->fiu[CH],s+1);
}

int sterge(Trie *nod,char *s)//sterge o aparitie a cuvantului
{
	if(*s>'z' || *s<'a')
		nod->nr--;
	  else 
	if(sterge(nod->fiu[CH],s+1)==1) 
	{
		nod->fiu[CH]=0;
		nod->nrfii--;
	}
	if(nod->nr==0 && nod->nrfii==0 && nod != T ) 
	{
		delete nod; return 1;
	}
	return 0;
}

int numara(Trie *nod,char *s)//numarul de aparitii ale cuvantului w in lista
{
	if(*s>'z' || *s<'a')
		return nod->nr;
	if(nod->fiu[CH])
		return numara(nod->fiu[CH],s+1);
	return 0;
}

int prefix(Trie *nod,char *s,int k)//tipareste lungimea celui mai lung prefix comun al lui w cu oricare cuvant din lista
{
	if(*s>'z' || *s<'a' || nod->fiu[CH]==0)
		return k;
	return prefix(nod->fiu[CH],s+1,k+1);
}

int main() 
{
	ifstream f("trie.in");ofstream g("trie.out");
	T=new Trie;
	while(f.getline(s,32)) 
	{
		if(s[0]=='0')adauga(T,s+2); else
		if(s[0]=='1')sterge(T,s+2); else
		if(s[0]=='2')g<<numara(T,s+2)<<'\n'; else
		if(s[0]=='3')g<<prefix(T,s+2,0)<<'\n';
	}
	f.close();g.close();
return 0;}