Problema de subsecuencia común más largo
La más larga subsecuencia común ( LCS ) problema es el problema de encontrar la más larga subsecuencia común a todas las secuencias en un conjunto de secuencias (a menudo apenas dos secuencias). Se diferencia del problema de subcadenas común más extenso : a diferencia de las subcadenas, no se requiere que las subsecuencias ocupen posiciones consecutivas dentro de las secuencias originales. El problema de subsecuencia común más extenso es un problema clásico de la informática , la base de los programas de comparación de datos , como la utilidad diff , y tiene aplicaciones en lingüística computacional y bioinformática . También es ampliamente utilizado porsistemas de control de revisión como Git para conciliar múltiples cambios realizados en una colección de archivos controlados por revisión.
Por ejemplo, considere las secuencias (ABCD) y (ACBAD). Tienen 5 subsecuencias comunes de longitud 2: (AB), (AC), (AD), (BD) y (CD); 2 subsecuencias comunes de longitud 3: (ABD) y (ACD); y subsecuencias ya no comunes. Entonces (ABD) y (ACD) son sus subsecuencias comunes más largas.
Para el caso general de un número arbitrario de secuencias de entrada, el problema es NP-difícil . [1] Cuando el número de secuencias es constante, el problema se puede resolver en tiempo polinomial mediante programación dinámica .
Dadas secuencias de longitudes , una búsqueda ingenua probaría cada una de las subsecuencias de la primera secuencia para determinar si también son subsecuencias de las secuencias restantes; cada subsecuencia se puede probar en el tiempo lineal en las longitudes de las secuencias restantes, por lo que el tiempo para este algoritmo sería
Para el caso de dos secuencias de n y m elementos, el tiempo de funcionamiento del enfoque de programación dinámica es O ( n × m ). [2] Para un número arbitrario de secuencias de entrada, el enfoque de programación dinámica ofrece una solución en
Existen métodos con menor complejidad, [3] que a menudo dependen de la longitud de la LCS, el tamaño del alfabeto o ambos.
