Subsecuencia común más larga

Una subsecuencia conserva los caracteres en orden, pero puede omitir algunos. De 'abcde' puede obtener 'ace', pero nunca 'aec'.

Dadas dos cadenas, la subsecuencia común más larga es la secuencia más larga que aparece en ambas y mantiene el mismo orden relativo.

Compare los prefijos de las dos cadenas. Una tabla bidimensional basada en sus longitudes convierte esto en una DP de cuadrícula conocida.

Sea dp[i][j] la longitud de la LCS de los primeros i caracteres de A y los primeros j caracteres de B.

Si A[i-1] es igual a B[j-1], esa letra compartida amplía la LCS. Sume uno al valor diagonal dp[i-1][j-1].

Si las letras son diferentes, elimine un carácter de cualquiera de las dos cadenas y conserve el mejor resultado. Tome el máximo de los dos vecinos.

Un prefijo vacío no comparte nada, así que la longitud de la LCS es cero. La fila 0 y la columna 0 permanecen llenas de ceros.

Dimensionar la tabla como n+1 por m+1 proporciona un borde de ceros gratuito. Así se eliminan las comprobaciones de límites en los extremos.

Recorra i y j empezando desde 1. Cada celda solo necesita los valores de arriba, de la izquierda y de la diagonal, que ya están calculados.

La longitud completa de la LCS se encuentra en la esquina. La respuesta es dp[n][m] una vez rellenadas todas las celdas.

Visita cada celda una vez, por lo que el trabajo requiere tiempo y memoria O(n por m). Esto permite trabajar cómodamente con cadenas de hasta unos pocos miles de caracteres.

Los caracteres actuales A[i-1] y B[j-1] son iguales. ¿Qué actualización es correcta?

Construya una tabla de n+1 por m+1: cuando haya coincidencia, sume uno a la diagonal; de lo contrario, tome el máximo de los vecinos. La esquina contiene la longitud. 🔗