//Trie 100 pct DINAMIC
#include <iostream>
#include <fstream>
#include <cstring>
#define ch (*s - 'a')
using namespace std;
struct Trie
{
    int nrfii, nrcuv;
    Trie *fiu[26];
    Trie () // constructor
    {
        nrfii = nrcuv = 0;
        memset(fiu, 0, sizeof(fiu));
    }
};
Trie *T = new Trie;
inline void Add(Trie *nod, char *s)
{
    if(*s == 0) // daca am terminat cuvantul de parcurs
    {
        nod->nrcuv++; // incrementez numarul de cuvinte care se termina la nod
        return;
    }
    if(nod->fiu[ch] == 0) // daca nodul nod nu are fiu pentru caracterul curent din s
    {
        nod->fiu[ch] = new Trie; // atunci creez fiul cu acel caracter
        nod->nrfii++; // incrementam si numarul de fii
    }
    Add (nod->fiu[ch], s+1); // trec la urmatorul caracter din sirul s;
                             // caracterul cu care am lucrat acum avand fiu creat
}

inline bool Delete(Trie *nod, char *s)
{
    if (*s == 0) // daca am terminat cuvantul de parcurs
    {
        nod->nrcuv--; // decrementez numarul de cuvinte care se termina in nod
    }
    else // daca mai am cuvant
    {
        if (Delete(nod->fiu[ch], s+1) == true) // daca am eliminat nodul fiu[ch]
        {
            nod->nrfii--; // decrementez numarul de fii
            nod->fiu[ch] = 0; // sterg fiul - il pregatesc pentru urmatoarele operatii
        }
    }
    if (nod->nrcuv == 0 && nod->nrfii == 0 && nod != T) // daca numai am cuvinte care se termina in nod si nici fii si nod != radacina
    {
        delete nod; // sterg nodul - eliberez memoria
        return true;
    }
    return false;
}
inline int Aparitii (Trie *nod, char *s)
{
    if (*s == 0) // daca am terminat cuvantul de parcurs
        return nod->nrcuv; // returnez numarul de cuvinte care se termina in nod
    if (nod->fiu[ch] != 0) // daca am fiu al lui nod specific caracterului curent din s
        return Aparitii (nod->fiu[ch], s+1); // merg la urmatorul nod;
    return 0;
}
inline int Prefix (Trie *nod, char *s, int k)
{
    if (*s == 0 || nod->fiu[ch] == 0) // daca am terminat cuvantul sau daca pentru litera curenta numai am nod - !!! nu se cauta un cuvant neaparat din trie
        return k; // returnez lungimea gasita;
    return Prefix (nod->fiu[ch], s+1, k+1);
}
int main()
{
    char linie[25];
    ifstream f ("trie.in");
    ofstream g ("trie.out");
    while (f.getline(linie, 25))
    {
        if (linie[0] == '0')
            Add (T, linie+2);
        if (linie[0] == '1')
            Delete (T, linie+2);
        if (linie[0] == '2')
            g<<Aparitii (T, linie+2)<<"\n";
        if (linie[0] == '3')
            g<<Prefix (T, linie+2, 0)<<"\n";
    }
    f.close();
    g.close();
    return 0;
}