Problem

1/10

Bor: el principio

Theory Click to read/hide

Barra
Bor es una estructura de datos para almacenar un conjunto de cadenas, que es un árbol arraigado con símbolos en los bordes. < /div>
Cada vértice de boro corresponde a un prefijo de alguna cadena añadida. Este prefijo en sí se obtiene escribiendo secuencialmente caracteres en los bordes del camino desde la raíz hasta este vértice. Al mismo tiempo, exactamente un vértice corresponde a cada prefijo existente. Bor root corresponde a una cadena vacía.

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



El naranja indica los vértices que corresponden a las palabras del propio conjunto. Se llaman terminales.

A continuación se muestra el código para almacenar el boro y agregarle líneas. Este método almacena la perforación a través de una matriz. También hay una implementación a través de punteros, que se presenta en el código de la tarea para el entrenamiento.
  // tamaño del alfabeto en las palabras consideradas const int alfa = 26; // estructura para la parte superior del taladro Nodo de estructura{ // vector de aristas en forma de tabla de adyacencia, es decir: // siguiente[0] - niño al saltar sobre el carácter número 0 ('a') // siguiente[1] - niño al saltar sobre el carácter número 1 ('b') // etc. vectorsiguiente; // Opciones adicionales // en este caso, la altura del vértice h y la bandera de terminalidad ent h; término bool;; Nodo(int h) { siguiente.redimensionar(alfa, -1); // inicialmente sin bordes esto->h = h; // la altura es igual a la especificada término=falso; // top no es terminal por defecto } }; // lista de vértices, inicialmente raíz a altura cero vector trie(1, Nodo(0)); // funcion para agregar una cadena al boro void add(const string& s) { int v = 0; // número del vértice actual, comenzando desde la raíz forn(i, (int)s.tamaño()) { int c = s[i] - 'a'; // obtener el número del carácter actual en la cadena // si la transición deseada aún no existe, haremos una nueva if (trie[v].siguiente[c] == -1) { trie[v].siguiente[c] = (int)trie.size(); // el nuevo número de vértice es   // tamaño de perforación actual (con numeración 0) trie.push_back(Nodo(trie[v].h + 1)); // crea un nuevo vértice con altura 1 más } v = prueba[v].siguiente[c]; // moverse a lo largo del borde deseado } // cuando llegamos a la cima,   // que coincide con toda la cadena,   // luego marcarlo como terminal prueba[v].término = verdadero; }
Si necesita apoyar la eliminación de filas del boro, probablemente resulte ser deshonesto. Es decir, simplemente elimine la bandera terminal (o, tal vez, en lugar de la bandera, necesitará almacenar un número variable) y deje el árbol de boro sin cambios.

Por lo tanto, la inserción/búsqueda/eliminación injusta funcionan en tiempo lineal a partir de la longitud de la cadena de consulta.

El propio boro, en el peor de los casos, ocupará la memoria O(n|Σ|), donde n es la longitud total de todas las cadenas, y Σ > - el alfabeto de las cadenas utilizadas.

Problem

Bor es una estructura eficiente de recuperación de información. Utilice esta estructura de datos para almacenar y buscar cadenas. 

Se requiere después de procesar las cadenas para averiguar si esta cadena existe en Bor.

Entrada
La primera línea contiene un único número entero N. En las siguientes líneas N, palabras formadas por letras minúsculas del alfabeto latino. A continuación, un único número entero K. En las siguientes líneas K, palabras formadas por letras minúsculas del alfabeto latino.
 
Salida
Imprima para cada cadena del segundo conjunto si existe en la estructura de datos ("Yes")  o no ("No".
 
Ejemplos

 

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++
# Entrada Salida
1
4
el
a
allí
respuesta
cualquiera
por
adiós
su
2
el
esto
 Sí
No
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!