#include <stdio.h>
#include <string.h>

struct trie{
   trie *litere[26];
   int nr_cuv;
   int aparitii;
   trie(){
     nr_cuv=aparitii=0;
	 memset(litere,0,sizeof(litere));
   }
};

int main(){
  FILE *fin=fopen("trie.in","r");
  FILE *fout=fopen("trie.out","w");
  int i,n;
  char buffer[30];
  char cuvant[25];
  int cod;
  trie *rad=new trie;
  trie *c; 
  while(!feof(fin)){
    fscanf(fin,"%[^\n]\n",buffer);
	sscanf(buffer,"%d %s",&cod,cuvant);
	switch(cod){
	  case 0:{//inserare
	     //pentru partea comuna
		 i=0;
		 c=rad;
		 n=strlen(cuvant);
		 while(i<n && c->litere[cuvant[i]-'a'] !=0){
		    c=c->litere[cuvant[i]-'a'];
		    c->nr_cuv++;
		    i++;
		 }
		 //pt partea noua
		 while(i<n){
		   c->litere[cuvant[i]-'a']=new trie;
		   c=c->litere[cuvant[i]-'a'];
		   c->nr_cuv++;
		   i++;
		 }
		 c->aparitii++;
	    break;
	  }
	  case 1:{//stergere (se garanteaza macar o aparitie)
	         i=0;
		 c=rad;
		 n=strlen(cuvant);
                 trie *stiva[25];
                 int vf=-1;
                 stiva[++vf]=rad;
		 while(i<n){
		    c=c->litere[cuvant[i]-'a'];
                    stiva[++vf]=c;
		    c->nr_cuv--;
		    i++;  
		 }
		 c->aparitii--;
                 if(c->aparitii==0 && c->nr_cuv==0){
                     //era ultimul de tipul lui si niciun cuvant nu depindea de el
                     while(c->nr_cuv==0 && vf>0){
                        stiva[vf-1]->litere[cuvant[vf-1]-'a']=0;
                        delete stiva[vf];
                        c=stiva[vf-1];
                        vf--;
                     }
                 }
	     break;
	  }
	  case 2:{//nr aparitii
	        i=0;
		c=rad;
                n=strlen(cuvant);
		while(i<n && c->litere[cuvant[i]-'a']!=0){
		     c=c->litere[cuvant[i]-'a'];
		     i++;
                }
	    if(i==n){
		   fprintf(fout,"%d\n",c->aparitii);
	    }else fprintf(fout,"0\n");
	  break;
	  }
	  case 3:{//cel mai lung sufix comun
              i=0;
              c=rad;
              n=strlen(cuvant);
	      while(i<n && c->litere[cuvant[i]-'a']!=0){
		      c=c->litere[cuvant[i]-'a'];
                      i++;
	      }
	    fprintf(fout,"%d\n",i);
	  break;
	  }
	  
	}
  }
return 0;
}