Tries: estrutura de dados para armazenar Strings

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 ao 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: \(O(Len)\). Len = tamanho da string.
• Procurar string: \(O(Len)\). 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 \(O(n * len)\) 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.

---

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