Celdas llenas
Pares coincidentes
La más larga hasta ahora

  • Llenándose
  • Leída
  • Respuesta

Más sobre la subsecuencia común más larga

Subsecuencia común más larga (LCS)

¿Qué letras tienen en común dos palabras, en el mismo orden? La subsecuencia común más larga responde a eso, y en ella se basan las herramientas diff, los correctores ortográficos y las comparaciones de ADN. Escribe dos palabras, mira cómo se llena una tabla con sus letras y luego reconstruye la respuesta desde la esquina. Pulsa Reproducir para ver cómo se llena la tabla, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. Escribe dos palabras: la primera va por el lateral de la tabla y la segunda por la parte de arriba. Cada celda guarda la longitud de la subsecuencia común más larga de las letras hasta su fila y su columna. Al final, las letras se leen de vuelta desde la celda de abajo a la derecha. Nuevo ejemplo elige otro par de palabras. Con el tablero seleccionado, las flechas avanzan o retroceden un paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.

Cómo funciona

  1. Escribe dos palabras: la primera va por el lateral de la tabla y la segunda por la parte de arriba.
  2. Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto.
  3. Mira cómo cada celda compara sus dos letras y luego sigue el camino naranja desde la esquina para leer la respuesta.

Cómo funciona la tabla

Una celda guarda la longitud de la subsecuencia común más larga entre las letras de la primera palabra hasta su fila y las letras de la segunda palabra hasta su columna. La fila y la columna marcadas con – representan una palabra vacía, así que valen 0. Si las dos letras de una celda son iguales, la celda vale uno más que la celda de arriba a la izquierda. Si son distintas, una de las dos letras no forma parte de la respuesta, así que la celda toma el mayor valor entre la celda de arriba y la de la izquierda.

Leer las letras de vuelta

La celda de abajo a la derecha es la longitud de la respuesta. Para encontrar las letras, empieza ahí: donde las dos letras coinciden, esa letra está en la subsecuencia y te mueves arriba a la izquierda; si no, te mueves a la mayor entre la celda de arriba y la de la izquierda. Las letras recogidas por el camino, leídas al revés, forman una subsecuencia común más larga. Puede haber otras de la misma longitud; la lectura inversa encuentra una de ellas.

Preguntas frecuentes

¿Qué diferencia hay entre una subsecuencia y una subcadena?

Una subcadena es una serie de letras seguidas, como ACE en RACER. Una subsecuencia mantiene el orden pero puede saltarse letras, así que ACE también es una subsecuencia de ABCDE. La subcadena común más larga es otro problema, con una tabla parecida.

¿Cuál es la velocidad del algoritmo LCS?

Para palabras de longitudes m y n, la tabla tiene m·n celdas, cada una rellenada en un paso, así que el trabajo es O(m·n). Para dos textos de 10.000 líneas son 100 millones de celdas, y por eso las herramientas diff usan métodos más ingeniosos basados en la misma idea.

¿Es única la subsecuencia común más larga?

No. ABCBDAB y BDCABA tienen tres subsecuencias comunes distintas de longitud 4: BCBA, BCAB y BDAB. La tabla da la longitud; la lectura inversa elige una de ellas.

¿Indica la LCS cuánto se parecen dos palabras?

En parte. Dos palabras de longitudes m y n cuya subsecuencia común más larga mide k pueden transformarse una en otra borrando m − k letras e insertando n − k. La distancia de edición, que también permite sustituir una letra, suele ser una medida mejor.

¿Se envía algo a algún sitio?

No. Todo se calcula en tu navegador, y tus últimos ajustes se quedan en el almacenamiento local de este navegador.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Ir al editor