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

FILE *f, *g;
typedef struct element{
    int endw, NrOfNodes;///fregventa cuvant, respectiv numar de fii directi
    short int poz[27]; /// reprezinta litere alfabetului 'a,b,c...z', marcheaza aparitia unui fiu
    struct element *next[27];///adresa urmatorului nod
}Trie;

Trie* CreateNod() {
    Trie* p = new Trie;
    p->endw = p->NrOfNodes = 0;
    for(int i = 0; i < 27; ++i) {
         p->next[i] = NULL;
         p->poz[i] = 0;
    }
    return p;
}

void AddTrie(Trie** root, char* cuv) {
    if(*root == NULL)/// arbore gol, se creaza un nou nod
        *root = CreateNod();
    int lengh = strlen(cuv) - 1;
    char c;
    Trie *last, *p = *root;
    for(int i = 0; cuv[i] != '\0'; ++i) {
        c = cuv[i] - 'a';
        if(!p->poz[c]) ///nod inca inexistent, se creaza si acesta
            p->poz[c] = 1;
            p->next[c] = CreateNod();
            ++(p->NrOfNodes);
        }
        last = p = p->next[c];
    }
    ++(last->endw);
}

void DeleteTrie(Trie** root, char* cuv) {
    if(*root == NULL)
        return;
    int lengh = strlen(cuv) - 1, m = -1;
    Trie* last, *queue[lengh + 2], *prev1 = NULL, *prev2 = NULL, *p = (*root);
    char c1, c2, c;
    for(int i = 0; cuv[i] != '\0'; ++i) {
        c = cuv[i] - 'a';
        if(!p->poz[c])///cuvantul nu se afla in arbore
            return;
        if(p->NrOfNodes == 1)///ratacina care are exact un fiu, un posibil candidat la stergere
            queue[++m] = p;
        else
            m = -1, prev1 = p, c1 = cuv[i];///stramosii adaugati in queue pana acum nu mai sunt relevanti, s-a gasit bifurcatie cu alt cuvant, ca atare nodurile gasite pana atunci cu potential de stergere nu mai sunt relevante
        prev2 = p, c2 = cuv[i];
        last = p = p->next[c];
    }
    if(!last->NrOfNodes && last->endw == 1) {///un cuvant poate fi eliberat din memorie daca nu are ascendenti
        free(last);
        last = NULL;
        --(prev2->NrOfNodes);///scade numarul de vecini ai nodului precedent in cazul in care se va sterge doar un nod
        prev2->poz[c2 - 'a'] = 0;
        for(int i = 0; i <= m; ++i) {///se sterge intreaga secventa de noduri care apartin numai si numai cuvantului nostru
            if(queue[i] == *root)///actualizam radacina daca arborele ramane gol
                *root = NULL;
            free(queue[i]);
        }
        if(m != -1 && prev1 != NULL) {///se actualizeaza si valorile precedente nodului de unde incepe secventa de noduri pe care le-am sters
            prev1->poz[c1 - 'a'] = 0;
            --(prev1->NrOfNodes);
        }
        return;
    }
    --(p->endw);///se elimina doar o fregventa
}

int PrintFreg(Trie* root, char* cuv) {
    if(root == NULL)
        return 0;
    int lengh = strlen(cuv) - 1;
    Trie* last;
    char c;
    for(int i = 0; cuv[i] != '\0'; ++i) {
        c = cuv[i] - 'a';
        if(!root->poz[c])///cuvant inexistent
            return 0;
        last = root = root->next[c];
    }
    return last->endw;///returnez fregventa
}

int PrintPref(Trie* root, char* cuv) {
    if(root == NULL) /// se prea poate ca in urma efectuarilor anumitor operatii, lista noastra sa devina goala
        return 0;
    int lenght = strlen(cuv) - 1, lgt = 0, maxfreq;
    Trie* last;
    char c;
    for(int i = 0; cuv[i] != '\0'; ++i) {
        c = cuv[i] - 'a';
        if(!root->poz[c]) /// am ajuns intr-un punct in care cuvantul nu exista
            return maxfreq;
        ++maxfreq;
        last = root = root->next[c];
    }
    return maxfreq;
}

int main() {
    f = fopen("trie.in", "r");
    g = fopen("trie.out", "w");
    char cuv[30];
    int operatie, k;
    Trie* root = NULL;
    while(fscanf(f,"%d %s", &operatie, &cuv) == 2) {
        switch(operatie) {
            case 0: /// se adauga un cuvant in Trie
                AddTrie(&root, cuv);
                break;
            case 1: /// se sterge un Trie
                DeleteTrie(&root, cuv);
                break;
            case 2: /// se determina fregventa unui cuvant
                k = PrintFreg(root, cuv);
                fprintf(g,"%d\n", k);
                break;
            case 3: /// se determina cel mai lung prefix a lui cuv cu orice cuvant din arbore
                k = PrintPref(root, cuv);
                fprintf(g,"%d\n", k);
                break;
        }
    }
    return 0;
}