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:
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; }