Complejidad Temporal
O(m × n)
LCS encuentra la subsecuencia más larga común a dos secuencias. Una subsecuencia es una secuencia que aparece en el mismo orden relativo, pero no necesariamente contigua.
Cómo funciona (DP Bottom-Up):
1. Crear una tabla 2D: dp[i][j] = longitud del LCS de los primeros i caracteres de X y los primeros j caracteres de Y
2. Si los caracteres coinciden: dp[i][j] = dp[i-1][j-1] + 1
3. Si no coinciden: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
4. dp[m][n] contiene la longitud del LCS
Complejidad Temporal: O(m × n)
Complejidad Espacial: O(m × n) — optimizable a O(min(m, n))
Aplicaciones:
- Herramientas diff (comparación de archivos)
- Alineamiento de secuencias de ADN
- Sistemas de control de versiones
- Corrección ortográfica
LCS es un problema fundamental en bioinformática y procesamiento de texto. Se generaliza al problema de distancia de edición.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Subsecuencia Común más Larga (LCS)?
- LCS encuentra la subsecuencia más larga común a dos secuencias. Una subsecuencia es una secuencia que aparece en el mismo orden relativo, pero no necesariamente contigua.
- ¿Cuál es la complejidad de Subsecuencia Común más Larga (LCS)?
- Tiempo (promedio): O(m × n) · Espacio: O(m × n)
- ¿Para quién es este visualizador de Subsecuencia Común más Larga (LCS)?
- La visualización de Subsecuencia Común más Larga (LCS) está pensada para nivel avanzado, dentro de la categoría Programación Dinámica. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Subsecuencia Común más Larga (LCS)?
- En la misma categoría (Programación Dinámica) puedes explorar: Fibonacci DP, Knapsack 0/1. Todos tienen visualización interactiva.