Categoría: Pattern Searching

Algoritmo de Manacher – Substring palindrómica más larga de tiempo lineal – Parte 4

Posted on by Rudeus Greyrat

En Algoritmo de Manacher Parte 1 y Parte 2 , repasamos algunos de los conceptos básicos, entendimos la array de longitud LPS y cómo calcularla de manera eficiente en base a cuatro casos. En la Parte 3 , implementamos lo mismo. Aquí revisaremos los cuatro casos nuevamente y trataremos de verlo de manera diferente e implementar … Continue reading «Algoritmo de Manacher – Substring palindrómica más larga de tiempo lineal – Parte 4»

Patrón de secuencia de montaña

Posted on by Rudeus Greyrat

Dado un número N , la tarea es generar el patrón de secuencia piramidal que contiene N pirámides una tras otra, como se muestra en los ejemplos a continuación. Ejemplos:  Input: N = 3 Output: * * * *** *** *** *************** Input: N = 4 Output: * * * * *** *** *** *** … Continue reading «Patrón de secuencia de montaña»

Compruebe si es posible llegar a (X, Y) desde (1, 1) siguiendo los pasos dados

Posted on by Rudeus Greyrat

Dados dos enteros X e Y , la tarea es verificar si es posible llegar a (X, Y) desde (1, 1 ) mediante los siguientes movimientos posibles: Desde un punto (a, b) tal que b > a , muévete hasta el punto (a, b – a) . Desde un punto (a, b) tal que a … Continue reading «Compruebe si es posible llegar a (X, Y) desde (1, 1) siguiendo los pasos dados»

Frecuencia de una substring en una string | conjunto 2

Posted on by Rudeus Greyrat

Dada una string str de longitud N y un patrón de substring de longitud M , la tarea es encontrar la frecuencia de aparición del patrón como una substring en la string dada. Si el patrón está presente en la string str , imprima » Sí » con el recuento de su aparición. De lo … Continue reading «Frecuencia de una substring en una string | conjunto 2»

Encuentre el último elemento restante después de la eliminación repetida de un elemento de pares de elementos de array adyacentes crecientes

Posted on by Rudeus Greyrat

Dada una array arr[] que consta de N enteros, la tarea es imprimir el último elemento restante de la array después de seleccionar repetidamente pares de elementos adyacentes crecientes (arr[i], arr[i + 1]) y eliminar cualquiera de los elementos de la array. par. Si no es posible reducir la array a un solo elemento, imprima … Continue reading «Encuentre el último elemento restante después de la eliminación repetida de un elemento de pares de elementos de array adyacentes crecientes»

Convierta una string binaria en otra cambiando los prefijos un número mínimo de veces

Posted on by Rudeus Greyrat

Dadas dos strings binarias A y B de longitud N , la tarea es convertir la string A en B cambiando repetidamente un prefijo de A , invirtiendo el orden de aparición de los bits en el prefijo elegido. Imprime el número de vueltas requeridas y la longitud de todos los prefijos. Ejemplos: Entrada: A … Continue reading «Convierta una string binaria en otra cambiando los prefijos un número mínimo de veces»

Cuente los caracteres de una string que, cuando se eliminan individualmente, hacen que la string sea igual a otra string

Posted on by Rudeus Greyrat

Dadas dos strings A y B de tamaño N y M respectivamente, la tarea es contar los caracteres de la string A , que cuando se eliminan individualmente igualan ambas strings. Si existen varios de estos caracteres, imprima sus respectivas posiciones. De lo contrario, imprima «-1» . Ejemplos: Entrada: A= “abaac”, B =“abac” Salida: 2 … Continue reading «Cuente los caracteres de una string que, cuando se eliminan individualmente, hacen que la string sea igual a otra string»

Encuentre el término N-ésimo en la serie 12, 35, 81, 173, 357, …

Posted on by Rudeus Greyrat

Dado un número N , la tarea es encontrar el N-ésimo término en la serie 12, 35, 81, 173, 357, … Ejemplo:   Input: N = 2 Output: 35 2nd term = (12*2) + 11 = 35 Input: N = 5 Output: 357 5th term = (12*(2^4))+11*((2^4)-1) = 357 Acercarse:   Todos y cada uno de los … Continue reading «Encuentre el término N-ésimo en la serie 12, 35, 81, 173, 357, …»

Reemplazar ‘?’ en una string tal que no hay dos caracteres adyacentes iguales

Posted on by Rudeus Greyrat

Dada una string S de longitud N que consta de «?» y minúsculas, la tarea es reemplazar «?» con letras minúsculas de modo que ningún carácter adyacente sea el mismo. Si existe más de una combinación posible, imprima cualquiera de ellas. Ejemplos: Entrada: S = “?a?a” Salida: baba Explicación: Reemplazar todos los ‘?’ con ‘b’ … Continue reading «Reemplazar ‘?’ en una string tal que no hay dos caracteres adyacentes iguales»

Suma de los dígitos del cuadrado del número dado que tiene solo 1 como dígitos

Posted on by Rudeus Greyrat

Dado un número representado como string str que consta del dígito 1 solamente, es decir , 1, 11, 111, … . La tarea es encontrar la suma de los dígitos del cuadrado del número dado. Ejemplos:  Entrada: str = 11  Salida: 4  11 2 = 121  1 + 2 + 1 = 4 Entrada: str … Continue reading «Suma de los dígitos del cuadrado del número dado que tiene solo 1 como dígitos»