/*    TRIE - LFA*/

#include<stdio.h>
#include<string.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()
{
    FILE *f=fopen("trie.in","rt");
    FILE *g=fopen("trie.out","wt");
    int op;
    char cuvi[20];
    while(!feof(f))
    {
    fscanf(f,"%i%s",&op,cuv);
    switch(op)
    {
    case 0:insert(p,cuvi);break;
    case 1:del(p,cuvi);break;
    case 2:fprintf(g,"%i\n",cuv(p,cuvi));break;
    case 3:fprintf(g,"%i\n",pref(p,cuvi,0));
    }
    }
fclose(f);
fclose(g);
return 0;
}
/*
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;
    return 1;
}
*/