#include <fstream>
#define alf 25
#define lcuv 21
using namespace std;
fstream f1 ("trie.in", ios::in);
fstream f2 ("trie.out", ios::out);
struct trie
{
    trie * ch[alf+1];
    int nrfii;///retine cate cuv cu litere urm distincte pleaca din nod
    int nrcuv;///retine nr de cuvinte care se termina in nodul dat
}*rad;
char cuv[lcuv];
void init(trie *&t)
{
    ///t= pointer catre trie, initial vid
    ///trie *t= new trie;
    t=new trie;

    t->nrfii=0;
    t->nrcuv=0;
    for(int i=0; i<=alf; i++)
        t->ch[i]=0;
}
void adauga(trie *t, char *cuv)
{
    if(*cuv!=0) ///daca ai litera de adaugat te duci pe nodul pe care trebuie sa o adaugi
    {
        if(t->ch[*cuv-'a']==0) ///daca nu exista pointer catre nodul respectiv
        {
            init(t->ch[*cuv-'a']);
            t->nrfii++;               ///numeri un nou pointer de la nodul t in jos
        }
        adauga(t->ch[*cuv-'a'], cuv+1);///adaugi urmatoarea litera in tree
    }
    else t->nrcuv++;///numeri un alt cuvant care se termina pe nodul t
}
void sterge(trie *t, char *cuv)
{
    if(*cuv!=0) ///daca ai litera de sters te duci pe nodul pe care trebuie sa o stergi
    {
       sterge(t->ch[*cuv-'a'], cuv+1);///stergi urmatoarea litera in tree

       if((t->ch[*cuv-'a']->nrfii==0)&&(t->ch[*cuv-'a']->nrcuv==0)&&(t->ch[*cuv-'a']!=rad)) ///daca nodul de jos trebuie sters
       {
        t->ch[*cuv-'a']=0; /// rupi legatura cu el
        delete t->ch[*cuv-'a'];
        t->nrfii--; ///nu mai numeri pointerul de la t in jos
       }
    }
    else ///nu mai numeri cuvantul care s-a terminat pe nodul t
    {
        t->nrcuv--;
    }
}
int nr_ap_cuv(trie* t, char *cuv)
{
     if(*cuv!=0)
     {
         if(t->ch[*cuv-'a']==0) return 0;///daca o litera din cuv nu se mai gaseste cuvantul nu apare
         else return nr_ap_cuv(t->ch[*cuv-'a'], cuv+1);
     }
     else return t->nrcuv; ////t->nrcuv !=0 doar daca t e nod terminal pt cel putin un cuv inserat
}
int lmax_pref(trie *t, char *cuv, int l)///l= lungimea curenta in apel a prefixului lui cuv
{
    if(*cuv!=0)
    {
        if(t->ch[*cuv-'a']==0) return l;///s-a terminat potrivirea din trie/t nu are fii
        else return lmax_pref(t->ch[*cuv-'a'], cuv+1, l+1);
    }
    else return l;
}
void operatii()
{
    int i;
    while(f1>>i>>cuv)
    {
        switch(i)
        {
            case 0: adauga(rad, cuv); break;
            case 1: sterge(rad, cuv); break;
            case 2: f2<<nr_ap_cuv(rad, cuv)<<"\n"; break;
            case 3: f2<<lmax_pref(rad, cuv, 0)<<"\n"; break;
        }
    }
}
int main()
{
    init(rad);
    operatii();
    return 0;
}