Module: Bor


Problem

1/10

Bor: O Começo

Theory Click to read/hide

Barra
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.

Problem

Bor é uma estrutura de recuperação de informação eficiente. Use esta estrutura de dados para armazenar e pesquisar strings. 

É necessário após o processamento das strings descobrir se esta string existe em Bor.

Entrada
A primeira linha contém um único inteiro N. Nas próximas N linhas, palavras que consistem em letras minúsculas do alfabeto latino. Em seguida, um único inteiro K. Nas próximas K linhas, palavras que consistem em letras minúsculas do alfabeto latino.
 
Saída
Imprima para cada string do segundo conjunto se ela existe na estrutura de dados ("Sim")  ou não ("Não".
 
Exemplos
# Entrada Saída
1
4
o
a
lá
resposta
qualquer
por
tchau
deles
2
o
isso
 Sim
Não

 

time 500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <iostream>
#include <string>
using namespace std;

const int ALPHABET_SIZE = 26;

// узел
struct TrieNode
{
  struct TrieNode *children[ALPHABET_SIZE];

  // isEndOfWord истинно, если на этой узле строка заканчивается 
  bool isEndOfWord;
};

// Возвращает новый узел
struct TrieNode *getNode(void)
{
  struct TrieNode *pNode = new TrieNode;
  pNode->isEndOfWord = false;

  for (int i = 0; i < ALPHABET_SIZE; i++)
    pNode->children[i] = NULL;

  return pNode;
}

//Вставляет новую строку
void insert(struct TrieNode *root, string key)
{
  struct TrieNode *pCrawl = root;

  for (int i = 0; i < key.length(); i++)
  {
    int index = key[i] - 'a';
    if (!pCrawl->children[index])
      pCrawl->children[index] = getNode();

    pCrawl = pCrawl->children[index];
  }

  // помечаем последнее слово
  pCrawl->isEndOfWord = true;
}

// Поиск ключа
bool search(struct TrieNode *root, string key)
{
  struct TrieNode *pCrawl = root;

  for (int i = 0; i < key.length(); i++)
  {
    int index = key[i] - 'a';
    if (!pCrawl->children[index])
      return false;

    pCrawl = pCrawl->children[index];
  }

  return (pCrawl != NULL && pCrawl->isEndOfWord);
}

int main()
{
  struct TrieNode *root = getNode();
	         
  return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!