Categoría: Pattern Searching

Búsqueda de patrones utilizando el árbol de sufijos – Part 1

Posted on by Rudeus Greyrat

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 – Part 1»

Divida la string binaria en substrings con el mismo número de 0 y 1

Posted on by Rudeus Greyrat

Dada una string binaria str de longitud N , la tarea es encontrar el recuento máximo de substrings consecutivas en las que str se puede dividir de manera que todas las substrings estén balanceadas, es decir, tengan el mismo número de 0 y 1 . Si no es posible dividir str cumpliendo las condiciones, imprima … Continue reading «Divida la string binaria en substrings con el mismo número de 0 y 1»

Algoritmo optimizado para la búsqueda de patrones – Part 1

Posted on by Rudeus Greyrat

Pregunta: Hemos discutido el algoritmo de coincidencia Naive String aquí . Considere una situación en la que todos los caracteres del patrón son diferentes. ¿Podemos modificar el algoritmo Naive String Matching original para que funcione mejor con este tipo de patrones? Si podemos, ¿cuáles son los cambios en el algoritmo original? Solución: en el algoritmo … Continue reading «Algoritmo optimizado para la búsqueda de patrones – Part 1»

Imprime un número como una string de ‘A’ y ‘B’ en orden lexicográfico

Posted on by Rudeus Greyrat

Dado un número N, la tarea es imprimir la string de ‘A’ y ‘B’ correspondiente a ese número. Si representamos todos los números como una string de ‘A’ y ‘B’ de la siguiente manera,   1 = A 2 = B 3 = AA 4 = AB 5 = BA 6 = BB 7 = AAA … Continue reading «Imprime un número como una string de ‘A’ y ‘B’ en orden lexicográfico»

Eliminaciones mínimas requeridas de modo que la string dada consista solo en un par de caracteres alternos

Posted on by Rudeus Greyrat

Dada una string S , la tarea es encontrar la eliminación mínima de caracteres necesaria para que la string S consista solo en dos caracteres alternos. Ejemplos: Entrada: S = “ adebbeeaebd” Salida: 7 Explicación: Eliminar todas las apariciones de ‘b’ y ‘e’ modifica la string a “adad”, que consiste en apariciones alternas de ‘a’ … Continue reading «Eliminaciones mínimas requeridas de modo que la string dada consista solo en un par de caracteres alternos»

Comprobar si un número comienza con otro número o no

Posted on by Rudeus Greyrat

Dados dos números A y B donde ( A > B ), la tarea es verificar si B es un prefijo de A o no. Escriba “Sí” si es un prefijo De lo contrario escriba “No” . Ejemplos:  Entrada: A = 12345, B = 12  Salida: Sí Entrada: A = 12345, B = 345  Salida: … Continue reading «Comprobar si un número comienza con otro número o no»

Mínimo y Máximo de todos los subarreglos de tamaño K usando Mapa

Posted on by Rudeus Greyrat

Dado un arreglo arr[] de N enteros y un entero K , la tarea es encontrar el mínimo y el máximo de todos los subarreglos de tamaño K. Ejemplos: Entrada: arr[] = {2, -2, 3, -9, -5, -8}, K = 4 Salida: -9 3 -9 3 -9 3 Explicación: A continuación se muestra el subarreglo … Continue reading «Mínimo y Máximo de todos los subarreglos de tamaño K usando Mapa»

Maximice la suma de las diferencias de elementos consecutivos después de eliminar exactamente K elementos

Posted on by Rudeus Greyrat

Dada una array ordenada arr[] de longitud N y un entero K tal que K < N , la tarea es eliminar exactamente K elementos de la array de modo que la suma de las diferencias de los elementos consecutivos de la array se maximice. Ejemplos:  Entrada: arr[] = {1, 2, 3, 4}, K = … Continue reading «Maximice la suma de las diferencias de elementos consecutivos después de eliminar exactamente K elementos»

Minimice el número de cortes necesarios para romper N varillas de longitud en N varillas de longitud unitaria

Posted on by Rudeus Greyrat

Dado un número entero N que denota la longitud de un palo dado, la tarea es minimizar el tiempo requerido para dividir el palo en pedazos de una unidad de longitud, dado que es posible un solo corte para cualquier porción de palo en cualquier instante de tiempo. Ejemplos:   Entrada: N = 100  Salida: 7  … Continue reading «Minimice el número de cortes necesarios para romper N varillas de longitud en N varillas de longitud unitaria»