Un árbol de segmentos alternos OR/XOR Levelwise es un árbol de segmentos, de modo que en cada nivel se alternan las operaciones OR y XOR. En otras palabras, en el Nivel 1, los subárboles izquierdo y derecho se combinan mediante la operación OR, es decir, el Node principal = Hijo izquierdo O Hijo derecho y … Continue reading «Operaciones alternas OR y XOR por niveles en el árbol de segmentos»
En Construcción del árbol de sufijos de Ukkonen – Parte 1 , hemos visto el Algoritmo de Ukkonen de alto nivel. Esta segunda parte es la continuación de la primera parte . Lea la Parte 1 antes de ver el artículo actual. En la construcción del árbol de sufijos de la string S de longitud … Continue reading «Construcción del árbol de sufijos de Ukkonen – Parte 2»
Una de las operaciones más comunes en strings es agregar o concatenar. Agregar al final de una string cuando la string se almacena de la manera tradicional (es decir, una array de caracteres) tomaría un tiempo mínimo de O (n) (donde n es la longitud de la string original). Podemos reducir el tiempo que lleva anexar … Continue reading «Estructura de datos de cuerdas (concatenación rápida de strings)»
Requisito previo: árboles genéricos (árboles de array N) En este artículo, discutiremos la conversión del árbol genérico a un árbol binario. Las siguientes son las reglas para convertir un árbol genérico (N-array Tree) en un árbol binario : La raíz del Árbol Binario es la Raíz del Árbol Genérico. El hijo izquierdo de un Node … Continue reading «Convertir un árbol genérico (árbol de array N) en un árbol binario»
Dada una array de N enteros positivos. La tarea es realizar las siguientes operaciones según el tipo de consulta dada. 1. Imprime el par máximo de productos en un rango dado. [LR] 2. Actualizar A i con algún valor dado. Ejemplos: Entrada: A={1, 3, 4, 2, 5} Consultas: Tipo 1: L = 0, R = 2. Tipo … Continue reading «Consultas para encontrar el par máximo de productos en el rango con actualizaciones»
Dados K vectores, la tarea es diseñar un iterador cíclico que imprima los elementos de estos vectores de manera cíclica. Por ejemplo: v1 = {1, 2, 3}, v2 = {4, 5, 6} y v3 = {7, 8, 9} entonces la salida debería ser 1, 4, 7, 2, 5, 8, 3 , 6 y 9 . … Continue reading «Iterador cíclico para K vectores de longitud variable»
Dada una serie de números de consultas de tamaño N y Q. Cada consulta o rango se puede representar mediante L (LeftIndex) y R (RightIndex). Encuentre la suma XOR de los números que aparecieron un número par de veces en el rango dado. Requisito previo: Consultas por número de números distintos en un rango dado. … Continue reading «XOR de números que aparecieron un número par de veces en un rango dado»
Trie es una estructura de datos de recuperación de información eficiente. Con Trie, las complejidades de búsqueda se pueden llevar a un límite óptimo (longitud de clave). Dado un intento. La tarea es imprimir los caracteres de forma ascendente. Recorrido ascendente : Primero imprima la string del subárbol más a la izquierda (de abajo hacia arriba), … Continue reading «Recorrido de abajo hacia arriba de un Trie»
Tenemos una array arr[0 . . . n-1]. Deberíamos poder encontrar de manera eficiente el valor mínimo desde el índice L (inicio de consulta) hasta R (final de consulta) donde 0 <= L <= R <= n-1 . Considere una situación en la que hay muchas consultas de rango. Ejemplo: Input: arr[] = {7, 2, 3, … Continue reading «Consulta de rango mínimo (descomposición de raíz cuadrada y tabla dispersa)»
Dado un texto txt[0..n-1] y un patrón pat[0..m-1], escriba una función de búsqueda (char pat[], char txt[]) que imprima todas las apariciones de pat[] en txt []. Puede suponer que n > m. ¿Patrón de preprocesamiento o texto de preprocesamiento? Hemos discutido los siguientes algoritmos en las publicaciones anteriores: Algoritmo KMP Algoritmo Rabin Karp Algoritmo … Continue reading «Búsqueda de patrones utilizando el árbol de sufijos»