#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f ("trie.in");
ofstream g ("trie.out");

/// explicatie principala https://infoarena.ro/problema/trie
/// facem o structura trie care contine frecventa cuvintelor de cate ori se repeta prefixele si un vector cu adrese pentru fiecare litera
/// vom nota frecventa unui cuvant doar in frunza acestuia (de ex la cuvantul "uite" nodul cu litera e va avea cuv = 1,iar toate literele vor avea prefixe = 1)
struct trie
{
    int cuv,prefixe;
    trie *copii[30];

    trie()
    {
        cuv = 0;
        prefixe = 0;
        for(int i = 0;i<30;i++)
            copii[i] = 0;
    }
};

/// functia de adaugare adauga prefixe si se opreste cand ajunge la finalul cuvantului unde incremenenteaza variabila cuv
void adaugare(trie *rad,char *c,int poz)
{
    rad->prefixe++;
    if(poz == strlen(c))
    {
        rad->cuv++;
        return;
    }

    /// aflam litera curenta in cuvant si in caz ca nu exista un nod pentru litera aceea care pleca din radacina curenta
    /// vom creea unul nou
    int litera = c[poz] - 'a';
    /// aceasta verificare == 0 se refera la NULL deoarece vectorul de copii este unul de adrese asa ca valoarea 0 se refera la NULL
    if(rad->copii[litera] == 0)
        rad->copii[litera] = new trie;

    /// apoi continuam adaugare cu urmatoare litera din cuvant
    adaugare(rad->copii[litera],c,poz+1);
}

/// functia de stergere scade prefixele prin care trece si la final scade frecventa cuvantului sters
void stergere(trie *rad,char *c,int poz)
{
    rad->prefixe--;
    if(poz == strlen(c))
    {
        rad->cuv--;
        return;
    }

    /// gasim litera din cuvantul de sters si continuam stergerea
    int litera = c[poz] - 'a';
    stergere(rad->copii[litera],c,poz+1);
}

/// functia incearca sa ajunga la finalul cuvantului cautat si in caz ca ajunge returneaza frecventa acestuia gasita in frunza cuvantului(nodul cu ultima litera)
int nr_aparitii(trie *rad,char *c,int poz)
{
    if(poz == strlen(c))
    {
        return rad->cuv;
    }
    /// gasim litera curenta din cuvantul pentru care cautam frecventa
    int litera = c[poz] - 'a';

    /// in caz ca vectorul de copii al radacinii nu are o adresa la pozitia litera sau prefixele copilului sunt == 0 atunci oprim cautarea
    /// deoarece daca nu gasim un prefix din cuvantul cautat inseamna ca nu vom gasi nici cuvantul

    ///*rad->copii[litera] == 0 , 0 reprezinta NULL deoarece vectorul de copii este unul de adrese
    if(rad->copii[litera] == 0 || rad->copii[litera]->prefixe == 0)
        return 0;

    return nr_aparitii(rad->copii[litera],c,poz+1);
}
/// functia incearca sa ajunga la finalul cuvantului si in caz de succes returneaza lungimea acestuia
int max_prefix_comun(trie *rad,char *c,int poz)
{
    if(poz == strlen(c))
    {
        return strlen(c);
    }
    /// gasim litera curenta din cuvantul pentru care cautam prefixul maxim
    int litera = c[poz] - 'a';

    /// in caz ca vectorul de copii al radacinii nu are o adresa la pozitia litera sau prefixele copilului sunt == 0 atunci oprim cautarea
    /// deoarece daca nu gasim un prefix din cuvantul cautat inseamna ca nu vom gasi nici  cuvantul asa ca returnam pozitia pana la care am ajuns
    /// deoarece noi cautam prefixul maxim
    if(rad->copii[litera] == 0 || rad->copii[litera]->prefixe == 0)
        return poz;

    return max_prefix_comun(rad->copii[litera],c,poz+1);
}
int main()
{
    int op;
    char ch[21];
    /// alocam memorie cu functia new unei variabile de tip trie
    /// o declaram cu * deoarece rad este un pointer - ca un i intr-un for care trece prin toate variabilele de tip trie
    trie *rad = new trie;
    while(f >> op >> ch)
    {
        switch(op)
        {
        case 0:
            adaugare(rad,ch,0);
            break;
        case 1:
            stergere(rad,ch,0);
            break;
        case 2:
            g << nr_aparitii(rad,ch,0)<<'\n';
            break;
        case 3:
            g << max_prefix_comun(rad,ch,0)<<'\n';
            break;
        }
    }

}