Subsecuencia común más larga
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 a 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.
Lo que queremos es encontrar la longitud de las subsecuencias comunes más largas de dos secuencias de caracteres dadas.
Entrada
La entrada está compuesta por diversos casos de prueba, estando cada uno de ellos formado por una línea en la que aparecen dos cadenas no vacías (de no más de 1.000 caracteres de la A a la Z) separadas por un espacio.
Salida
Para cada caso de prueba se debe escribir la longitud de las subsecuencias comunes más largas de las dos cadenas leídas.
Entrada de ejemplo
AMAPOLA MATAMOSCAS AAA BBBB ATAMOS MATAMOSCAS
Salida de ejemplo
4 0 6