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

#define alphabetSize 26
#define wordSize 100

FILE *in, *out;
struct Trie
{
    int nr;
    int nrSons;
    struct Trie **next;
};
typedef struct Trie Trie;

void insert(char *word, Trie *trie);
int delete(char *word, Trie *trie);
void query(char *word, Trie *trie);
void prefix(char *word, Trie *trie, int len);

int main()
{
    int op, l = 0;
    char word[wordSize];
    Trie *trie = calloc(1, sizeof(Trie));

    in = fopen("trie.in", "r");
    out = fopen("trie.out", "w");
    
    while(EOF != fscanf(in, "%d %s", &op, word))
    {
    	l++;
    	printf("%d %d %s\n", l, op, word);
        switch(op)
        {
            case 0:
                insert(word, trie);
                break;
            case 1:
                delete(word, trie);
                break;
            case 2:
                query(word, trie);
                break;
            default:
                prefix(word, trie, 0);
        }
    }

    fclose(in);
    fclose(out);
    return 0;
}

void prefix(char *word, Trie *trie, int len)
{
    if(*word == '\0')
        fprintf(out, "%d\n", len);
    else
    {
        if(trie->next && trie->next[*word - 'a'])
            prefix(word + 1, trie->next[*word - 'a'], len + 1);
        else
            fprintf(out, "%d\n", len);
    }
}

void query(char *word, Trie *trie)
{
    if(*word == '\0')
        fprintf(out, "%d\n", trie->nr);
    else
    {
    	if(trie->next && trie->next[*word - 'a'])
	        query(word + 1, trie->next[*word - 'a']);
	    else
	    	fprintf(out, "0\n");
	}
}

int delete(char *word, Trie *trie)
{
    if(*word == '\0')
    {
        trie->nr--;
        if(trie->nr == 0 && trie->nrSons == 0)
        {
            free(trie->next);
            trie->next = NULL;
            return 1;
        }
        return 0;
    }
    else
    {
        if(delete(word + 1, trie->next[*word - 'a']))
        {
            free(trie->next[*word - 'a']);
            trie->next[*word - 'a'] = NULL;
            trie->nrSons--;
        }

        if(trie->nr == 0 && trie->nrSons == 0)
        {    
            free(trie->next);
            trie->next = NULL;
            return 1;
        }
        return 0;
    }
}

void insert(char *word, Trie *trie)
{
    if(*word == '\0')
        trie->nr++;
    else
    {
        if(trie->next == NULL)
            trie->next = calloc(alphabetSize, sizeof(Trie*));
        if(trie->next[*word - 'a'] == NULL)
            trie->next[*word - 'a'] = calloc(1, sizeof(Trie)),
            trie->nrSons++;
        
        insert(word + 1, trie->next[*word - 'a']);
    }
}