Las sublistas comunes de “1325” y “36572” son “”, “3”,”32″, “35”, “2” y “5”. El máximo de sus longitudes es 2.
Definir la función
maximo :: Eq a => [a] -> [a] -> Int |
tal que (maximo xs ys) es el máximo de las longitudes de las sublistas comunes de xs e ys. Por ejemplo,
maximo "1325" "36572" == 2 maximo [1,4..33] [2,4..33] == 5 maximo [1..10^6] [1..10^6] == 100000 |
Soluciones
import Data.List (subsequences, intersect) -- 1ª definición -- ============= maximo1 :: Eq a => [a] -> [a] -> Int maximo1 xs ys = maximum (map length (sublistasComunes xs ys)) -- (sublistasComunes xs ys) es la lista de las sublistas comunes de xs e -- ys. Por ejemplo, sublistasComunes :: Eq a => [a] -> [a] -> [[a]] sublistasComunes xs ys = subsequences xs `intersect` subsequences ys -- 2ª definición -- ============= maximo2 :: Eq a => [a] -> [a] -> Int maximo2 l1@(x:xs) l2@(y:ys) | x == y = 1 + maximo2 xs ys | otherwise = max (maximo2 xs l2) (maximo2 l1 ys) maximo2 _ _ = 0 -- Comparación de eficiencia -- ========================= -- λ> maximo1 [1,4..30] [2,4..30] -- 5 -- (3.60 secs, 0 bytes) -- λ> maximo2 [1,4..30] [2,4..30] -- 5 -- (1.58 secs, 216,347,472 bytes) -- -- λ> maximo2 [1..10^6] [1..10^6] -- 1000000 -- (2.44 secs, 407,051,096 bytes) |
(MUY POCO EFICIENTE)
Una mejora de mi anterior versión:
En Maxima