Encontrar todas las formas posibles de insertar un patrón en una cadena

He estado pensando en este problema por un tiempo, y solo puedo encontrar una solución recursiva, pero siento que hay una forma de programación dinámica para hacerlo, simplemente no puedo resolverlo. ¿Es este un problema famoso que no conozco?

P: Dada una cadena y un patrón, devuelve el número de formas únicas de hacer coincidir las letras del patrón (en orden) con la cadena.

Aclaración: para encontrar una coincidencia, toma el primer carácter del patrón, busca el primer carácter coincidente en la cadena, luego toma el segundo carácter del patrón y coincide con el primer carácter coincidente de la cadena que es DESPUÉS de su coincidencia anterior personaje.

Ejemplo 1 (4 coincidencias):

Cadena: DABBCDDE

Patrón: ABD

Formas posibles (los caracteres en negrita son donde el patrón coincide con la cadena):

D AB BC D DE
D A B B C D DE
D AB BCD D E
D A B B CD D E

Ejemplo 2 (0 coincidencias):

Cadena: ABC

Patrón: BCA

(Coincides con B, C y luego estás al final de la cadena, NO puedes volver atrás y unir caracteres anteriores)

Con el enfoque recursivo, tengo un método que realiza un seguimiento de qué índice estoy en la cadena ( sIndex ), así como el patrón ( pIndex ). Si la cadena [sIndex] coincide con el patrón [pIndex], llamamos al método nuevamente y aumentamos sIndex y pIndex. Si no, simplemente aumente sIndex e intente nuevamente encontrar una coincidencia. El método devuelve el número total porque el valor de retorno de las llamadas recursivas se suman. (Las coincidencias agregan 1, ninguna coincidencia agrega 0)

Casos base:

Si pIndex es mayor que la longitud del patrón, devuelve 0.
Si sIndex es mayor que la longitud de la cadena, devuelve 1 (¡encontramos una coincidencia!)

¿Qué otras soluciones hay?

algorithms recursion dynamic-programming Daniel Olsson
fuente

¿Se permiten valores duplicados en el patrón? ¿Estamos garantizados que tanto el patrón como la cuerda están en orden?

Brandon Arnold

Sí, se permiten valores duplicados en el patrón. No sé si me hice demasiado claro, pero si codificas la orden, entonces el problema cambia. Entonces, si tiene CBA como cadena y el patrón es ABC, no tiene coincidencias porque la primera coincidencia es la A, y luego no hay más caracteres en la cadena para que coincidan con los caracteres restantes en el patrón (BC). ¿Lo deja claro?

Daniel Olsson

Me parece insertingbastante engañoso. ¿No están estos elementos coincidentes patterncon elementos stringen orden de todas las formas posibles?

Mai

Eliminé mi respuesta regex, porque después de jugar en js fiddle descubrí que no coincide con todas las permutaciones posibles :(

Gavin Clarke

Mai, eso es cierto, cambiaré la redacción.

Daniel Olsson

Respuestas:

Creo que no necesita usar la programación dinámica para resolver esto. Creo que esta es la solución:

Primero haga la lista de listas para mantener las apariciones de caracteres en el patrón en el texto dado.
Será asi

El siguiente diagrama:

   A    B    D 
             0 
   1 -> 2 -> 5
        3    6

Esto implica (suponiendo que la indexación 0) A ocurra en la posición 0, B ocurra en las posiciones 2,3, D ocurra en las posiciones 0,5,6.
Para cada uno de los pares de columnas consecutivas (aquí A, B y B, D) use punteros para mapear los valores correspondientes en una columna a los siguientes valores mayores en la siguiente columna. Aquí 1 (en col1) tiene un puntero a 2 (en col2) y 2 (en col2) tiene un puntero a 5 (en col3) ya que 0 es menor que 2. 3 (en col2) tiene un puntero a 5 (en col3 ) (No pude dibujar aquí).
Para cada valor en la primera columna, encuentre el número de formas posibles utilizando los punteros. Aquí 1 -> 2 y 2 -> 5 y, por lo tanto, el número de formas posibles es 2 * 2 formas (es decir, 1-> 2-> 5, 1-> 2-> 6, 1-> 3-> 5, 1 -> 3-> 6). Solo tiene que multiplicar el número de elementos restantes en la columna por cada valor de A.
Aquí solo está presente 1 valor para la Columna1 (es decir, A). Si hay varias columnas, calculamos el valor de cada valor de A usando los punteros y sumamos todos para obtener el número de formas.
Creo que la complejidad es O (n), ya que la lista de construcción es O (n), el espacio de punteros y el tiempo de construcción es O (n).

kaushalpranav
fuente

Esto es correcto, pero debe ser más específico sobre la generación de las ocurrencias de las letras del patrón. La complejidad para eso es O (nm) donde n es la longitud del patrón ym la longitud del texto. (Necesitamos encontrar todas las ocurrencias de cada lettern en el patrón).

Adrian Buzea