Categoría: Pattern Searching

Imprime todas las strings en la array dada que ocurren como la substring en la string dada

Posted on by Rudeus Greyrat

Dada una array de strings arr[] y una string str , la tarea es imprimir todas las strings en arr[] que aparecen como una substring en str . Ejemplo: Entrada: str =”geeksforgeeks”, arr[] ={ “forg”, “geek”, “ek”, “dog”, “sfor”} Salida:  forg geek ek sfor Explicación: Las strings “forg”, “geek” , «ek» y «sfor» aparecen como … Continue reading «Imprime todas las strings en la array dada que ocurren como la substring en la string dada»

Verifique si la secuencia de movimientos dada es circular con una repetición infinita

Posted on by Rudeus Greyrat

Dada una string str que denota una secuencia de movimientos. La tarea es verificar si los movimientos se repiten un número infinito de veces, entonces los movimientos estarán enlazados en una trayectoria circular o no. Los movimientos pueden ser de los siguientes tipos: “G”: ir derecho 1 unidad; “L”: giro de 90 grados a la … Continue reading «Verifique si la secuencia de movimientos dada es circular con una repetición infinita»

Programa Javascript para verificar si una string es una substring de otra

Posted on by Rudeus Greyrat

Dadas dos strings s1 y s2, encuentre si s1 es una substring de s2. En caso afirmativo, devuelve el índice de la primera aparición, de lo contrario, devuelve -1. Ejemplos:  Input: s1 = «for», s2 = «geeksforgeeks» Output: 5 Explanation: String «for» is present as a substring of s2. Input: s1 = «practice», s2 = … Continue reading «Programa Javascript para verificar si una string es una substring de otra»

MEX de secuencia generada de N+1 enteros donde i-ésimo entero es XOR de (i-1) y K

Posted on by Rudeus Greyrat

Dados dos números enteros N y K , genere una secuencia de tamaño N+1 donde el i -ésimo elemento sea (i-1)⊕K , la tarea es encontrar el MEX de esta secuencia. Aquí, el MEX de una secuencia es el entero no negativo más pequeño que no ocurre en la secuencia. Ejemplos: Entrada : N = … Continue reading «MEX de secuencia generada de N+1 enteros donde i-ésimo entero es XOR de (i-1) y K»

Programa C++ para verificar si las strings son rotaciones entre sí o no | conjunto 2

Posted on by Rudeus Greyrat

Dadas dos strings s1 y s2, compruebe si s2 es una rotación de s1. Ejemplos:  Input : ABACD, CDABA Output : True Input : GEEKS, EKSGE Output : True Hemos discutido un enfoque en una publicación anterior que maneja la coincidencia de substrings como un patrón. En esta publicación, utilizaremos la construcción lps (prefijo propio más … Continue reading «Programa C++ para verificar si las strings son rotaciones entre sí o no | conjunto 2»

Encuentre la posición i para dividir la array de manera que el prefijo sum hasta i-1, i y el sufijo sum hasta i+1 estén en GP con una relación común K

Posted on by Rudeus Greyrat

Dada una array , arr[] y un entero positivo K. La tarea es encontrar la posición, digamos i , del elemento en arr[] tal que el prefijo suma hasta i-1 , i y  el sufijo suma hasta i+1 estén en Progresión geométrica con una relación común K. Ejemplos : Entrada : arr[] = { 5, … Continue reading «Encuentre la posición i para dividir la array de manera que el prefijo sum hasta i-1, i y el sufijo sum hasta i+1 estén en GP con una relación común K»

Número más grande formado por X e Y con la cuenta de X divisible por Y y de Y por X

Posted on by Rudeus Greyrat

Dados tres enteros X , Y y N , la tarea es encontrar el mayor número posible de longitud N que consista solo en X e Y como sus dígitos, de modo que la cuenta de X en él sea divisible por Y y viceversa . Si no se puede formar tal número, imprima -1 … Continue reading «Número más grande formado por X e Y con la cuenta de X divisible por Y y de Y por X»

Construcción del árbol de sufijos de Ukkonen – Parte 5

Posted on by Rudeus Greyrat

Este artículo es la continuación de los siguientes cuatro artículos: Construcción del árbol de sufijos de Ukkonen – Parte 1 Construcción del árbol de sufijos de Ukkonen – Parte 2 Construcción del árbol de sufijos de Ukkonen – Parte 3 Construcción del árbol de sufijos de Ukkonen – Parte 4 Lea la Parte 1 , … Continue reading «Construcción del árbol de sufijos de Ukkonen – Parte 5»

Búsqueda de patrones | Conjunto 6 (Construcción eficiente de autómatas finitos)

Posted on by Rudeus Greyrat

En la publicación anterior , discutimos el algoritmo de búsqueda de patrones basado en Finite Automata. El método de construcción FA (Finite Automata) discutido en la publicación anterior toma O ((m ^ 3) * NO_OF_CHARS) tiempo. FA se puede construir en tiempo O(m*NO_OF_CHARS). En esta publicación, discutiremos el algoritmo O(m*NO_OF_CHARS) para la construcción de FA. … Continue reading «Búsqueda de patrones | Conjunto 6 (Construcción eficiente de autómatas finitos)»

Cuente las ocurrencias de un elemento en una array de tamaño N * N generada de manera que cada elemento sea igual al producto de sus índices | Conjunto-2

Posted on by Rudeus Greyrat

-Dados dos enteros positivos N y X , la tarea es contar las ocurrencias del entero X dado en una array cuadrada de longitud N generada de manera que cada elemento de la array sea igual al producto de sus índices de fila y columna ( 1- indexación basada ). Ejemplos: Entrada: N = 5, … Continue reading «Cuente las ocurrencias de un elemento en una array de tamaño N * N generada de manera que cada elemento sea igual al producto de sus índices | Conjunto-2»