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

struct trie
{
    int nrs,cnt; /// nrs = number of sons (numarul de fii), cnt = contorul de cuvinte
    trie *son [26]; /// son = vector de pointeri catre fii unui nod (poninterul null inseamna ca nu exista acel fiu)
    trie ()
    {
        cnt=nrs=0; ///numarul de cuvinte dintr-un nod si numarul de fii sunt setate la 0
        memset(son,0,sizeof(son));
    }
};

char s[35]; /// stringul pe care o sa lucram
trie *root = new trie(); /// cream radacina trie-ului , care va avea valoarea initiala asociata egala cu 0

void insert_word (trie *node ,char *s)
{
    if (*s==NULL) /// daca am ajuns la capatul unui cuvant (mai exact la caracterul null)
    {
        node->cnt ++; /// incrementam numarul de cuvinte care se termina intr-un nod
        return ;
    }

    int delta = *s - 'a'; /// calculam a catea litere din alfabet e litera actuala

    if (node->son[delta]==NULL) /// in caz ca nu avem fiul (nodul) de la litera ceruta, cream fiul (nodul) si incrementam numarul de fii
    {
        node->son[delta]= new trie();
        node->nrs ++;
    }

    insert_word (node->son[delta],s+1); /// functia va continua pana cand ajungem la capatul cuvantului
}

int word_frequency (trie *node , char *s)
{
    if (*s==NULL) /// daca am ajuns la capatul unui cuvant (mai exact la caracterul null)
        return node->cnt; /// returnam numarul de cuvinte dintr-un nod

    int delta = *s - 'a'; /// calculam a catea litere din alfabet e litera actuala

    if (node->son[delta]==NULL) /// daca ajungem intr-un nod de unde cuvantul nostru nu mai este continuat
        return 0; /// returnam frecventa 0 a cuvantului dorit

    word_frequency(node->son[delta],s+1); /// functia va continua pana cand ajungem la capatul cuvantului
}

int longest_common_prefix (trie *node , char *s)
{
    if (*s==NULL) /// daca am ajuns la capatul unui cuvant
        return 0; /// returnam 0

    int delta = *s - 'a'; /// calculam a catea litere din alfabet e litera actuala

    if (node->son[delta]==NULL) /// daca ajungem intr-un nod care nu mai are fiu din cuvantul dorit
        return 0; /// am ajuns la sfarsitul prefixului comun si returnam 0

    return 1+longest_common_prefix(node->son[delta],s+1);
}

bool erase_word (trie *node , char *s) /// stergere si din memorie a unui nod
{
    if (*s==NULL) /// cazul in care am ajuns la capatul unui cuvant
    {
        node->cnt--; /// scadem numarul actual de cuvinte dintr-un nod
        if (node->cnt==0 && node->nrs==0 && node!=root) /// daca nodul (fizic, din memorie) poate fi sters
        {
            delete node; /// il stergem
            return 1; /// returnam valoarea 1, asta insemnand ca a fost sters un nod
        }
        return 0; /// returnam valoarea 0, asta insemnand ca nu a fost sters un nod
    }
    int delta = *s - 'a';

    if (erase_word(node->son[delta],s+1)) /// cazul in care suntem in cuvant iar nodul literei urmatoare a fost sters
    {
        node->nrs--; /// scadem numarul de fii
        node->son[delta] = 0; /// nulificam pointerul catre nodul literei urmatoare

        if (node->cnt==0 && node->nrs==0 && node!=root) /// daca nodul (fizic, din memorie) poate fi sters
        {
            delete node; /// il stergem
            return 1; /// returnam valoarea 1, asta insemnand ca a fost sters un nod
        }
    }

    return 0; /// daca nu s-a returnat pana acum vreo valoare, returnam 0, asta insemnand ca nu a fost sters un nod
}

int main()
{
    int op;
    /*
    0 w - adauga o aparitie a cuvantului w in lista
    1 w - sterge o aparitie a cuvantului w din lista
    2 w - tipareste numarul de aparitii ale cuvantului w in lista
    3 w - tipareste lungimea celui mai lung prefix comun al lui w cu oricare cuvant din lista
    */
    while (f>>op>>s)
    {
        if (op==0)
            insert_word(root,s);
        if (op==1)
            erase_word(root,s);
        if (op==2)
            g<<word_frequency(root,s)<<'\n';
        if (op==3)
            g<<longest_common_prefix(root,s)<<'\n';

    }
    return 0;
}