Bor

Bor é uma estrutura de dados para armazenar um conjunto de strings, que é uma árvore enraizada com símbolos nas bordas. < /div>
Cada vértice de boro corresponde a um prefixo de alguma string adicionada. Esse prefixo em si é obtido escrevendo caracteres sequencialmente nas arestas do caminho da raiz até esse vértice. Ao mesmo tempo, exatamente um vértice corresponde a cada prefixo existente. Bou root corresponde a uma string vazia.

Exemplo de boro para {be, bee, can, cat, cd}



Laranja indica os vértices que correspondem às palavras do próprio conjunto. Eles são chamados terminais.

Abaixo está o código para armazenar o boro e adicionar linhas a ele. Este método armazena o furo por meio de uma matriz. Existe também uma implementação através de ponteiros, que é apresentada no código da tarefa para treinamento.
  // tamanho do alfabeto em palavras consideradas const int alfa = 26; // estrutura para o topo da furadeira struct Nó{ // vetor de arestas em forma de tabela de adjacência, ou seja: // próximo[0] - filho ao pular sobre o caractere número 0 ('a') // próximo[1] - filho ao pular sobre o personagem número 1 ('b') // etc. vetorpróximo; // Opções extras // neste caso, a altura do vértice h e o sinalizador de terminalidade int h; termo bool;; Nó(int h) { next.resize(alph, -1); // inicialmente sem arestas este->h = h; // altura é igual a especificada termo=falso; // top não é terminal por padrão } }; // lista de vértices, inicialmente raiz na altura zero vetor trie(1, Nó(0)); // função para adicionar uma string ao boro void add(const string& s) { int v = 0; // número do vértice atual, começando pela raiz forn(i, (int)s.size()) { int c = s[i] - 'a'; // obtém o número do caractere atual na string // se a transição desejada ainda não existe, então faremos uma nova if (trie[v].next[c] == -1) { trie[v].next[c] = (int)trie.size(); // o novo número do vértice é   // tamanho do drill atual (com numeração 0) trie.push_back(Node(trie[v].h + 1)); // cria um novo vértice com altura 1 a mais } v = trie[v].próximo[c]; // move ao longo da aresta desejada } // quando chegamos ao topo,   // que corresponde a toda a string,   // em seguida, marque-o como terminal trie[v].termo = verdadeiro; }
Se você precisar apoiar a exclusão de linhas do boro, provavelmente será desonesto. Ou seja, simplesmente remova o sinalizador terminal (ou, talvez, em vez do sinalizador, você precisará armazenar um número variável) e deixe a própria árvore de boro inalterada.

Assim, inserção/pesquisa/exclusão injusta funcionam em tempo linear a partir do comprimento da string de consulta.

O próprio boro, no pior caso, ocupará a memória O(n|Σ|), onde n é o comprimento total de todas as strings e Σ > - o alfabeto das strings usadas.