Calculadora LCS

El problema de la subsecuencia común más larga pide la secuencia de caracteres más larga que aparece en el mismo orden dentro de dos cadenas de entrada, sin exigir contigüidad. Es la base de programación dinámica de las herramientas de diff por líneas, ayudas de fusión en control de versiones, detectores de plagio que toleran reordenaciones ruidosas y la comparación de secuencias biológicas cuando las inserciones y eliminaciones importan más que un substring exacto. Esta calculadora de subsecuencia común más larga acepta dos cadenas, rellena una tabla clásica de longitudes en tiempo lineal respecto al producto de las longitudes, reconstruye un LCS válido por retroceso y devuelve tanto la longitud numérica como la cadena de la subsecuencia. Las entradas vacías son válidas y dan longitud cero.

Qué es (y qué no es) una subsecuencia común más larga

Una subsecuencia de una cadena es cualquier cadena obtenida al borrar cero o más caracteres sin reordenar los que quedan. Una subsecuencia común de dos cadenas es una cadena que es subsecuencia de ambas. Una subsecuencia común más larga, o LCS, es cualquier subsecuencia común cuya longitud es máxima entre todas las subsecuencias comunes.

A diferencia de un substring común más largo, un LCS no necesita ocupar un bloque contiguo en ninguna de las entradas: el par clásico ABCBDAB y BDCABA admite varias cadenas LCS de longitud cuatro, como BCBA y BDAB, según qué empates elija la reconstrucción. Los algoritmos de diff y las herramientas de alineamiento de DNA se basan en esta noción no contigua porque las ediciones reales insertan y eliminan símbolos en lugar de solo deslizar una ventana fija.

La longitud de un LCS es una puntuación de similitud útil; los caracteres reconstruidos sirven cuando usted quiere un esqueleto de alineamiento explícito junto a la puntuación. No devuelve todos los LCS posibles, scripts de edición ni porcentajes de similitud: esos son problemas distintos construidos sobre la misma idea de tabla DP.

Dónde resulta útil la subsecuencia común

Los cursos de informática y los jueces en línea necesitan un oráculo de referencia que devuelva una longitud correcta y una subsecuencia válida para cadenas cortas arbitrarias sin que el alumnado pegue soluciones en un IDE completo. Las funciones de producto cercanas al diff—resúmenes de cambios, pistas de conflicto de fusión, alineación de líneas de log—suelen querer la longitud LCS como señal barata de similitud antes de un pase más pesado de distancia de edición.

Las demos docentes de bioinformática usan cadenas del alfabeto DNA de juguete (A, C, G, T) para mostrar cómo inserciones y eliminaciones dejan aun así un esqueleto compartido largo. Mantenga las cadenas bajo el tope de longitud, fije la subsecuencia reconstruida en las pruebas si le importa cuál de varias respuestas igual de largas obtiene, y tendrá resultados LCS reproducibles sin montar una biblioteca numérica propia.