#define _CRT_SECURE_NO_WARNINGS

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

#define ALPHABET_SIZE 26

typedef struct trieNode {
    char letter;
    int frequency;
    struct trieNode* children[ALPHABET_SIZE];
}trieNode;

trieNode* createNode(char letter) {
    trieNode* newNode = (trieNode*)malloc(sizeof(trieNode));
    newNode->letter = letter;
    newNode->frequency = 0;
    for (int i = 0; i < ALPHABET_SIZE; i++)
        newNode->children[i] = NULL;

    return newNode;
}

void addWord(trieNode* root, char* word) {
    trieNode* currentLetter = root;
    for (int i = 0; word[i] != NULL; i++) {
        int index = word[i] - 'a';
        if (currentLetter->children[index] == NULL)
            currentLetter->children[index] = createNode(word[i]);
        currentLetter = currentLetter->children[index];
    }

    currentLetter->frequency++;
}

bool deleteWord(trieNode* node, char* word, int length) {
    if (strlen(word) == length) {
        node->frequency--;

        for (int i = 0; i < ALPHABET_SIZE; i++)
            if (node->children[i] != NULL)
                return false;
        if (node->frequency > 0)
            return false;
        return true;
    }

    int index = word[length] - 'a';
    bool shouldDelete = deleteWord(node->children[index], word, length + 1);
    if (shouldDelete == true) {
        free(node->children[index]);
        node->children[index] = NULL;
        if (node->frequency == 0) {
            for (int i = 0; i < ALPHABET_SIZE; i++)
                if (node->children[i] != NULL)
                    return false;
            return true;
        }
        return false;
    } 
    
    return false;
}

int wordFrequency(trieNode* root, char* word) {
    trieNode* currentLetter = root;
    for (int i = 0; word[i] != NULL; i++) {
        int index = word[i] - 'a';
        if (currentLetter->children[index] == NULL)
            return 0;
        currentLetter = currentLetter->children[index];
    }

    return currentLetter->frequency;
}

int longestCommonPrefixLength(trieNode* root, char* word) {
    trieNode* currentLetter = root;
    int length = 0;
    for (int i = 0; word[i] != NULL; i++) {
        int index = word[i] - 'a';
        if (currentLetter->children[index] == NULL)
            return length;
        currentLetter = currentLetter->children[index];
        length++;
    }

    return length;
}

void main(int argc, char* argv[]) {
    FILE* input = fopen("trie.in", "r");
    if (input == NULL) {
        printf("Error\n");
        exit(1);
    }

    FILE* output = fopen("trie.out", "w");
    if (output == NULL) {
        printf("Error\n");
        exit(2);
    }

    int operation;
    char word[21];
    trieNode* root = createNode('!');

    while (fscanf(input, "%d %s", &operation, word) == 2) {
        if (operation == 0) {
            addWord(root, word);
        } else if (operation == 1) {
            deleteWord(root, word, 0);
        } else if (operation == 2) {
            int frequency = wordFrequency(root, word);
            fprintf(output, "%d\n", frequency);
        } else if (operation == 3) {
            int commonPrefixLength = longestCommonPrefixLength(root, word);
            fprintf(output, "%d\n", commonPrefixLength);
        }
    }

    fclose(input);
    fclose(output);
}