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

#define LINE_LEN		64
#define ALPHABET_SIZE		26
#define GET_INDEX(letter)	((letter) - 'a')

struct node {
	struct node  *next[ALPHABET_SIZE];
	unsigned int num_appearances;
};

static void alloc_node(struct node **root)
{
	*root = calloc(1, sizeof(struct node));
	assert(*root != NULL);
}

static int destroy_node(struct node **root)
{
	struct node **next;
	int i;
	int can_destroy = 1;

	if (*root == NULL)
		return 1;

	if ((*root)->num_appearances != 0)
		return 0;

	for (i = 0; i < ALPHABET_SIZE; i++) {
		next = &(*root)->next[i];
		can_destroy = can_destroy && destroy_node(next);
	}

	if (can_destroy) {
		free(*root);
		*root = NULL;
	}

	return can_destroy;
}

static void add_appearance(struct node **root, char *word)
{
	char c = word[0];
	struct node **next;

	if (c == '\0') {
		(*root)->num_appearances++;
		return;
	}

	next = &(*root)->next[GET_INDEX(c)];

	if (*next == NULL)
		alloc_node(next);

	add_appearance(next, word + 1);
}

static void remove_appearance(struct node **root, char *word)
{
	char c = word[0];
	struct node **next;

	if (*root == NULL)
		return;

	if (c == '\0') {
		(*root)->num_appearances--;
		if ((*root)->num_appearances == 0)
			destroy_node(root);
		return;
	}

	next = &(*root)->next[GET_INDEX(c)];
	remove_appearance(next, word + 1);
}

static int get_num_appearances(struct node **root, char *word)
{
	char c = word[0];
	struct node **next;

	if (*root == NULL)
		return 0;

	if (c == '\0')
		return (*root)->num_appearances;

	next = &(*root)->next[GET_INDEX(c)];
	return get_num_appearances(next, word + 1);
}

static int get_prefix_len(struct node **root, char *word)
{
	char c = word[0];
	struct node **next;

	next = &(*root)->next[GET_INDEX(c)];

	if (c == '\0' || *next == NULL)
		return 0;

	return get_prefix_len(next, word + 1) + 1;
}

int main()
{
	struct node	*root;
	char		op[LINE_LEN], *cptr;
	int		op_code, num_ap, pr_len;;
	FILE		*fin, *fout;

	// Open files:
	fin = fopen("trie.in", "r");
	assert(fin != NULL);
	fout = fopen("trie.out", "w");
	assert(fout != NULL);

	// Allocate root node:
	alloc_node(&root);

	// Read lines:
	while (1) {
		// Read one line:
		cptr = fgets(op, LINE_LEN, fin);
		if (cptr == NULL)
			break;
		op[strlen(op) - 1] = '\0'; // Remove '\n'

		// Get op code:
		op_code = op[0] - '0';

		// Get word:
		cptr = op + 2;

		// Process command:
		switch (op_code) {
			case 0:
				add_appearance(&root, cptr);
				break;
			case 1:
				remove_appearance(&root, cptr);
				break;
			case 2:
				num_ap = get_num_appearances(&root, cptr);
				fprintf(fout, "%d\n", num_ap);
				break;
			case 3:
				pr_len = get_prefix_len(&root, cptr);
				fprintf(fout, "%d\n", pr_len);
				break;
			default:
				break;
		};

	}

	// Free resources:
	destroy_node(&root);
	fclose(fin);
	fclose(fout);

	return 0;
}