As Tries são uma estrutura de dados para armazenar strings. Tem a vantagem de ser muito rápida e de ter a capacidade de partilhar posições das strings que queremos guardar, sendo assim eficiente também a nível de memória.

Basicamente vamos ter em cada nó um vector de ponteiros que vai ser o nosso "abecedário", ou seja, poderá ter, por exemplo, 26 posições. Se determinada letra existir na string a partir de determinado nó, criamos uma nova estrutura do mesmo tipo da anterior.

No final da string marcamos numa flag que é mesmo o final da string para não existirem problemas na pesquisa de strings.

Complexidade:

• Inserção de uma string: . Len = tamanho da string.
• Procurar string: . Len = tamanho da string.

A partir daqui já podemos ver que a complexidade é muito boa visto que se guardássemos as strings num vector, teríamos uma complexidade de em que n é o número de strings e len é o tamanho máximo de cada string - temos que percorrer todas as strings e comparar uma a uma com a que queremos encontrar.

Vou deixar aqui uma imagem com a estrutura. http://www.topcoder.com/i/education/alg_tries.png

O código fica assim:

#include <cstdio>
#include <cstring>
 
using namespace std;
 
const int MAX = 255;
 
typedef struct Trie
{
	struct Trie *children[MAX];
	bool is_end;
} trie;
 
void init_node (trie *node)
{
	for (int k = 0; k < MAX; k++) 
		node -> children[k] = NULL;
 
	node -> is_end = false;
}
 
void add_word (char *str, trie *head)
{
	trie *walk = head;
 
	for (int k = 0; str[k]; k++)
	{
		if (walk -> children[str[k]] == NULL)
		{
			walk -> children[str[k]] = new trie;
			init_node (walk -> children[str[k]]);
		}
		walk = walk -> children[str[k]];
	}
 
	walk -> is_end = true;
}
 
bool find_word (char *str, trie *head)
{
	trie *walk = head;
 
	for (int k = 0; str[k]; k++)
	{
		if (walk -> children[str[k]] == NULL) 
			return false;
		walk = walk -> children[str[k]];
	}
	if (walk -> is_end == true) 
		return true;
}
 
int main ()
{
	char input[MAX];
	trie *head = new trie;
 
	init_node (head);
 
	scanf ("%s", input);
	while (strcmp (input, "stop") != 0)
	{
		add_word (input, head);
		scanf ("%s", input);
	}
 
	scanf ("%s", input);
	while (strcmp (input, "exit") != 0)
	{
		if (find_word (input, head) == true) 
			printf ("String found!\n");
 
		else 
			printf ("String not found!\n");
 
		scanf ("%s", input);
	}
 
	return 0;
}