Miembro : Login |Registro |Subir conocimiento
Buscar
El problema de subsecuencia común más largo [Modificación ]
El problema de la subsecuencia común más larga (LCS) es el problema de encontrar la subsecuencia más larga común a todas las secuencias en un conjunto de secuencias (a menudo solo dos secuencias). Se diferencia del problema de subcadena común más largo: a diferencia de las subcadenas, no se requiere subsecuencias para ocupar posiciones consecutivas dentro de las secuencias originales. El problema de subsecuencia común más largo es un problema clásico de informática, la base de los programas de comparación de datos, como la utilidad diff, y tiene aplicaciones en bioinformática. También es ampliamente utilizado por los sistemas de control de revisiones como Git para conciliar los cambios múltiples realizados en una colección de archivos controlada por revisión.
[Bioinformática][Control de versiones]
1.Complejidad
2.Solución para dos secuencias
2.1.Prefijos
2.2.Primera propiedad
2.3.Segunda propiedad
2.4.Función LCS definida
2.5.Ejemplo trabajado
2.6.Enfoque de seguimiento
3.Relación con otros problemas
4.Código para la solución de programación dinámica
4.1.Calculando la longitud del LCS
4.2.Leyendo un LCS
4.3.Lectura de todos los LCS
4.4.Imprimir la diferencia
4.5.Ejemplo
5.Optimización de código
5.1.Reducir el conjunto de problemas
5.2.Reducir el tiempo de comparación
5.3.Reducir cadenas a hashes
5.4.Reduce el espacio requerido
5.5.Más algoritmos optimizados
6.Comportamiento en cadenas aleatorias
[Subir Más Contenido ]


Derechos de autor @2018 Lxjkh