#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define ALPHABET_SIZE 26

struct TrieNode
{
    struct TrieNode *children[ALPHABET_SIZE];
    int count;
    int endHere;
};

struct Trie
{
    struct TrieNode *root;
};

void initTrie(struct Trie *trie)
{
    trie->root = (struct TrieNode *)malloc(sizeof(struct TrieNode));
}

void insertWord(struct TrieNode *root, const char *word)
{
    for (int i = 0; i < strlen(word); ++i)
    {
        if (root->children[word[i] - 'a'] != NULL)
        {
            root = root->children[word[i] - 'a'];
            ++root->count;
        }
        else
        {
            root->children[word[i] - 'a'] = (struct TrieNode *)malloc(sizeof(struct TrieNode));
            root = root->children[word[i] - 'a'];
            ++root->count;
        }
    }
    ++root->endHere;
}

int countWord(struct TrieNode *root, const char *word)
{
    for (int i = 0; i < strlen(word); ++i)
    {
        if (root->children[word[i] - 'a'] != NULL)
        {
            root = root->children[word[i] - 'a'];
        }
        else
        {
            return 0;
        }
    }
    return root->endHere;
}

int longestPrefix(struct TrieNode *root, const char *word)
{
    int result = 0;
    for (int i = 0; i < strlen(word); ++i)
    {
        if (root->children[word[i] - 'a'] != NULL)
        {
            root = root->children[word[i] - 'a'];
            if (root->count)
            {
                result = i + 1;
            }
        }
        else
        {
            break;
        }
    }
    return result;
}

void eraseWord(struct TrieNode *root, const char *word)
{
    printf("%s\n", word);
    if (strlen(word) > 0)
    {
        printf("entered\n");
        eraseWord(root->children[word[0] - 'a'], word + 1);
        if (root->count)
        {
            --root->count;
        }
    }
    else
    {
        --root->endHere;
        --root->count;
    }


}

void freeTrie(struct TrieNode *root)
{
    for (int i = 0; i < ALPHABET_SIZE; ++i)
    {
        if (root->children[i] != NULL)
        {
            freeTrie(root->children[i]);
        }
    }
    free(root);
}

int main()
{
    struct Trie trie;
    int type;
    char *word;

    FILE *in = fopen("trie.in", "r");
    FILE *out = fopen("trie.out", "w");

    initTrie(&trie);
    while (fscanf(in, "%d %s", &type, word) != EOF)
    {
        // printf("%d %s\n", type, word );
        if (type == 0)
        {
            insertWord(trie.root, word);
        }
        else if (type == 1)
        {
            eraseWord(trie.root, word);
        }
        else if (type == 2)
        {
            fprintf(out, "%d\n", countWord(trie.root, word));
        }
        else if (type == 3)
        {
            fprintf(out, "%d\n", longestPrefix(trie.root, word));
        }
    }

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