Sobre el longest common subsequence: extensiones y algoritmos

Abstract

Dadas dos palabras x e y sobre un alfabeto finito cualquiera, el problema de la Longest Common Subsequence (LCS) en castellano Subsecuencia Común Más Larga consiste, como su nombre sugiere, en encontrar cuál es el largo máximo que puede tener una palabra que sea subsecuencia de x e y simultáneamente. El presente artículo muestra una revisión y análisis de las diferentes extensiones y técnicas algorítmicas más conocidas hasta el momento y que dan solución a este problema.