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

#define TAM 26

typedef struct trie_no{
	int folha;
	struct trie_no *filhos[TAM];
} Trie_No;

Trie_No* cria_no()
{
	Trie_No *no = (Trie_No*)malloc(sizeof(Trie_No));
	int i;
	no->folha = 0;
	for (i = 0; i < TAM; i++)
	{
		no->filhos[i] = NULL;
	}
	return no;
}

void insere(Trie_No *no, char *palavra)
{
	int tam = strlen(palavra);
	int i, indice;
	Trie_No *atual = no;
	for (i = 0; i < tam; i++)
	{
		indice = ((int)palavra[i] - (int)'a');
		if (atual->filhos[indice] == NULL)
		{
			atual->filhos[indice] = cria_no();
		}
		atual = atual->filhos[indice];
	}
	atual->folha = 1;
}

int busca(Trie_No *no, char *palavra)
{
	int tam = strlen(palavra);
	int i, indice;
	Trie_No *atual = no;
	for (i = 0; i < tam; i++)
	{
		indice = ((int)palavra[i] - (int)'a');
		if (atual->filhos[indice] == NULL)
		{
			return 0;
		}
		else
		{
			atual = atual->filhos[indice];
		}		
	}
	return atual->folha;
}

int main()
{
	int i;
	char *palavras[] = {"bear", "bell", "bid", "bull", "buy", "sell", "stock", "stop"};
	Trie_No *trie = cria_no();

	for (i = 0; i < 8; i++)
	{
		insere(trie, palavras[i]);
	}

	printf("%d\n", busca(trie, "bear"));
	
	return 0;
}