/*    TRIE - LFA*/

#include<iostream>
#include<conio.h>

#define STR (*s - 'a')

using namespace std;


typedef struct trie
{
       int nrCuv;               // nr de cuvinte care se termina in nodul curent
       int nrFii;               // nr de cuvinte care au cuvantul pana la nodul curent drept prefix
       trie *fiu[26];           // pt fiecare litera a alfabetului
       trie()
       {
             nrCuv = 0;
             nrFii = 0;
             memset(fiu, 0, sizeof(fiu));
       }
} Trie;

Trie *p = new trie;


void insert(Trie *cuvant, char *s)
{
     if(*s == '\n')
     {
            cuvant->nrCuv++;
            return;
     }
     if(cuvant->fiu[STR] == NULL)
     {
            cuvant->fiu[STR] = new Trie;
            cuvant->nrFii++;
     }
     insert(cuvant->fiu[STR], s + 1);
} 

int del(Trie *cuvant, char *s)
{
    if(*s = '\n')
    {
          cuvant->nrCuv--;
          return 0;
    }       
    else if( del(cuvant->fiu[STR], s + 1))
         {
             cuvant->fiu[STR] = 0;
             cuvant->nrFii--;     
         }
         if(cuvant->nrCuv == 0 && cuvant->nrFii == 0 && cuvant != p)  // daca nu are cuvinte care se termina in el, nu mai are nici fii si nu e nici radacina
         {
             delete cuvant;
             return 1;
         }
    return 0;
}

int cuv(Trie *cuvant, char *s)
{
    if(*s = '\n') return cuvant->nrCuv;
    
    if(cuvant->fiu[STR])
         return cuv(cuvant->fiu[STR], s + 1);
    return 0;
}

int pref(Trie *cuvant, char *s, int k = 0)
{
    if(*s = '\n' && cuvant->fiu[STR] == 0) return k;
    return pref( cuvant->fiu[STR], s+1, k+1 );
}

int main()
{
    int i;
    char s[32];
    FILE *in = fopen("trie.txt", "r");
    FILE *out = fopen("trieOut.txt", "w");
    while(fscanf(in,"%d %s",&i,s) != EOF)
    {
     if(i == 0)
                     insert(p,0);
     if(i == 1)
                     del(p,0);
     if(i == 2)
                     printf( "%d\n", cuv( p, s+2 ) ); 
     if(i == 3)
                     printf( "%d\n", pref( p, s+2, 0 ) );
    }
    fclose(in);
    fclose(out);
    return 0;
    getch();
    return 1;
}