bor

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.