Longitud de la subsecuencia común máxima (con programación dinámica)

Si a una secuencia X de elementos (pongamos por ejemplo, caracteres) le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparecían originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, «aaoa» es una subsecuencia de la secuencia «amapola».

El término también se aplica cuando quitamos todos los elementos (es decir, la secuencia vacía es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de sí misma).

Dadas dos secuencias X e Y, decimos que Z es una subsecuencia común de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = «amapola» e Y = «matamoscas», la secuencia «aaoa» es una de las subsecuencias comunes de X e Y más larga, con longitud 4, ya que no hay ninguna subsecuencia común a X e Y de longitud mayor que 4. También son subsecuencias comunes de longitud 4 «maoa» o «amoa».

Se desea encontrar la longitud de las subsecuencias comunes más largas de dos secuencias de caracteres dadas.

Definir la función

tal que longitudSCM xs ys es la longitud de la subsecuencia máxima de xs e ys. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python