{"id":2212,"date":"2016-03-09T05:00:24","date_gmt":"2016-03-09T03:00:24","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2212"},"modified":"2016-03-16T06:56:50","modified_gmt":"2016-03-16T04:56:50","slug":"maxima-longitud-de-las-sublistas-comunes","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/maxima-longitud-de-las-sublistas-comunes\/","title":{"rendered":"M\u00e1xima longitud de las sublistas comunes"},"content":{"rendered":"<p>Las sublistas comunes de \u00ab1325\u00bb y \u00ab36572\u00bb son \u00ab\u00bb, \u00ab3\u00bb,\u00bb32&#8243;, \u00ab35\u00bb, \u00ab2\u00bb y \u00ab5\u00bb. El m\u00e1ximo de sus longitudes es 2.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   maximo :: Eq a => [a] -> [a] -> Int\n<\/pre>\n<p>tal que (maximo xs ys) es el m\u00e1ximo de las longitudes de las sublistas comunes de xs e ys. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   maximo \"1325\" \"36572\"       == 2\n   maximo [1,4..33] [2,4..33]  == 5\n   maximo [1..10^6] [1..10^6]  == 100000\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (subsequences, intersect)\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nmaximo1 :: Eq a => [a] -> [a] -> Int\nmaximo1 xs ys = \n    maximum (map length (sublistasComunes xs ys))\n\n-- (sublistasComunes xs ys) es la lista de las sublistas comunes de xs e\n-- ys. Por ejemplo,\nsublistasComunes :: Eq a => [a] -> [a] -> [[a]]\nsublistasComunes xs ys =\n    subsequences xs `intersect` subsequences ys\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\nmaximo2 :: Eq a => [a] -> [a] -> Int\nmaximo2 l1@(x:xs) l2@(y:ys) \n    | x == y    = 1 + maximo2 xs ys\n    | otherwise = max (maximo2 xs l2) (maximo2 l1 ys)  \nmaximo2 _ _ = 0\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> maximo1 [1,4..30] [2,4..30]\n--    5\n--    (3.60 secs, 0 bytes)\n--    \u03bb> maximo2 [1,4..30] [2,4..30]\n--    5\n--    (1.58 secs, 216,347,472 bytes)\n--    \n--    \u03bb> maximo2 [1..10^6] [1..10^6]\n--    1000000\n--    (2.44 secs, 407,051,096 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Las sublistas comunes de \u00ab1325\u00bb y \u00ab36572\u00bb son \u00ab\u00bb, \u00ab3\u00bb,\u00bb32&#8243;, \u00ab35\u00bb, \u00ab2\u00bb y \u00ab5\u00bb. El m\u00e1ximo de sus longitudes es 2. Definir la funci\u00f3n maximo :: Eq a => [a] -> [a] -> Int tal que (maximo xs ys) es el m\u00e1ximo de las longitudes de las sublistas comunes de xs e ys. Por ejemplo,&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[270,28,10,15,11,88],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2212"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=2212"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2212\/revisions"}],"predecessor-version":[{"id":2241,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2212\/revisions\/2241"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2212"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2212"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2212"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}