¿Es correcto este método de subcadena común más larga?

Question

He encontrado un algoritmo para Subcadena común más larga.Generalmente se hace usando dynamic programming, usando una matriz 2-D de tamaño mxn dónde m y n son longitudes de las dos cuerdas consideradas.

Construiré la siguiente matriz para las dos cadenas.

M[i][j] = 1 if s1[i]==s2[j] else 0.

Por ejemplo, si las cadenas son: abcxy y pqaabx

La matriz queda de la siguiente manera:

    a b c x y
 p  0 0 0 0 0
 q  0 0 0 0 0
 a  1 0 0 0 0
 a  1 0 0 0 0
 b  0 1 0 0 0
 x  0 0 0 1 0

Ahora busco una secuencia continua máxima de 1s en cada diagonal que está en la dirección de arriba a la izquierda a abajo a la derecha.

El valor máximo entre estos será la respuesta.

Puedo realizar la operación anterior sin usar la matriz explícitamente.La complejidad temporal sigue siendo O(M*N).Por tanto, no hay necesidad de memoria.

¿Alguien puede indicarme dónde me estoy equivocando?

Answer 1

Su método es correcto.Para la prueba, supongamos que la subcadena común más larga para S1 y S2 fue de S1 [i..j] y S2 [P..Q]. esto implica S1 [I + k]= S2 [P + K]

Todos estos se encuentran en la diagonal a partir de (I, P).

La solución de programación dinámica hace lo mismo, pero en lugar de calcular la tabla primero y pasando por las rutas diagonales, calcula la tabla dependiendo de su padre diagonal, además de que coinciden o no.

editado

En su comentario en la solución Wikipedia utilizando memoria adicional.Está ahí solo para mayor claridad.En principio, solo necesita dos filas de la matriz en la solución Wikipedia y mantenga el recuento máximo actual en una variable.Esto es correcto ya que para cualquier entrada (i, j) th en la matriz

m (i, j)= 1 + M (I-1, J-1) (si S1 [I]== S2 [J])

Como puede ver, los elementos de fila actuales dependen solo de los elementos de la fila superior inmediatamente.

Answer 2

Su algoritmo es correcto, pero el enfoque DP estándar elimina su segunda fase y hace que la solución sea más sencilla.

En lugar de marcar los valores booleanos y luego escanear las diagonales para buscar secuencias más largas, puede calcular las longitudes diagonales a medida que construye la matriz, solo se requiere una pasada.

En términos de complejidad de tiempo y espacio, ambas soluciones son O (NXM).Su solución puede guardar alguna memoria si usa una representación de una matriz de bits, mientras que la otra solución es probablemente un poco más rápida.