{"id":7513,"date":"2022-11-14T06:00:11","date_gmt":"2022-11-14T04:00:11","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7513"},"modified":"2022-12-14T11:44:31","modified_gmt":"2022-12-14T09:44:31","slug":"14-nov-22","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/14-nov-22\/","title":{"rendered":"Reconocimiento de subcadenas"},"content":{"rendered":"

Definir, por recursi\u00f3n, la funci\u00f3n<\/p>\n

\n   esSubcadena :: String -> String -> Bool\n<\/pre>\n
tal que esSubcadena xs ys<\/code> se verifica si xs<\/code> es una subcadena de ys<\/code>. Por ejemplo,<\/p>\n
\n   esSubcadena \"casa\" \"escasamente\"   ==  True\n   esSubcadena \"cante\" \"escasamente\"  ==  False\n   esSubcadena \"\" \"\"                  ==  True\n<\/pre>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nesSubcadena1 :: String -> String -> Bool\nesSubcadena1 [] _      = True\nesSubcadena1  _ []     = False\nesSubcadena1 xs (y:ys) = xs `isPrefixOf` (y:ys) || xs `esSubcadena1` ys\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nesSubcadena2 :: String -> String -> Bool\nesSubcadena2 xs ys =\n  or [xs `isPrefixOf` zs | zs <- sufijos ys]\n\n-- (sufijos xs) es la lista de sufijos de xs. Por ejemplo,\n--    sufijos \"abc\"  ==  [\"abc\",\"bc\",\"c\",\"\"]\nsufijos :: String -> [String]\nsufijos xs = [drop i xs | i <- [0..length xs]]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nesSubcadena3 :: String -> String -> Bool\nesSubcadena3 xs ys =\n  or [xs `isPrefixOf` zs | zs <- tails ys]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nesSubcadena4 :: String -> String -> Bool\nesSubcadena4 xs ys =\n  any (xs `isPrefixOf`) (tails ys)\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nesSubcadena5 :: String -> String -> Bool\nesSubcadena5 = (. tails) . any . isPrefixOf\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\nesSubcadena6 :: String -> String -> Bool\nesSubcadena6 = isInfixOf\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_esSubcadena :: String -> String -> Bool\nprop_esSubcadena xs ys =\n  all (== esSubcadena1 xs ys)\n      [esSubcadena2 xs ys,\n       esSubcadena3 xs ys,\n       esSubcadena4 xs ys,\n       esSubcadena5 xs ys,\n       esSubcadena6 xs ys]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_esSubcadena\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> esSubcadena1 \"abc\" (replicate (5*10^4) 'd' ++ \"abc\")\n--    True\n--    (0.03 secs, 17,789,392 bytes)\n--    \u03bb> esSubcadena2 \"abc\" (replicate (5*10^4) 'd' ++ \"abc\")\n--    True\n--    (6.32 secs, 24,989,912 bytes)\n--\n--    \u03bb> esSubcadena1 \"abc\" (replicate (5*10^6) 'd' ++ \"abc\")\n--    True\n--    (3.24 secs, 1,720,589,432 bytes)\n--    \u03bb> esSubcadena3 \"abc\" (replicate (5*10^6) 'd' ++ \"abc\")\n--    True\n--    (1.81 secs, 1,720,589,656 bytes)\n--    \u03bb> esSubcadena4 \"abc\" (replicate (5*10^6) 'd' ++ \"abc\")\n--    True\n--    (0.71 secs, 1,120,589,480 bytes)\n--    \u03bb> esSubcadena5 \"abc\" (replicate (5*10^6) 'd' ++ \"abc\")\n--    True\n--    (0.41 secs, 1,120,589,584 bytes)\n--    \u03bb> esSubcadena6 \"abc\" (replicate (5*10^6) 'd' ++ \"abc\")\n--    True\n--    (0.11 secs, 560,589,200 bytes)\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef esSubcadena1(xs: str, ys: str) -> bool:\n    if not xs:\n        return True\n    if not ys:\n        return False\n    return ys.startswith(xs) or esSubcadena1(xs, ys[1:])\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# sufijos(xs) es la lista de sufijos de xs. Por ejemplo,\n#    sufijos(\"abc\")  ==  ['abc', 'bc', 'c', '']\ndef sufijos(xs: str) -> list[str]:\n    return [xs[i:] for i in range(len(xs) + 1)]\n\ndef esSubcadena2(xs: str, ys: str) -> bool:\n    return any(zs.startswith(xs) for zs in sufijos(ys))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef esSubcadena3(xs: str, ys: str) -> bool:\n    return xs in ys\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.text(), st.text())\ndef test_esSubcadena(xs: str, ys: str) -> None:\n    r = esSubcadena1(xs, ys)\n    assert esSubcadena2(xs, ys) == r\n    assert esSubcadena3(xs, ys) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q reconocimiento_de_subcadenas.py\n#    1 passed in 0.35s\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('esSubcadena1(\"abc\", \"d\"*(10**4) + \"abc\")')\n#    0.02 segundos\n#    >>> tiempo('esSubcadena2(\"abc\", \"d\"*(10**4) + \"abc\")')\n#    0.01 segundos\n#    >>> tiempo('esSubcadena3(\"abc\", \"d\"*(10**4) + \"abc\")')\n#    0.00 segundos\n#\n#    >>> tiempo('esSubcadena2(\"abc\", \"d\"*(10**5) + \"abc\")')\n#    1.74 segundos\n#    >>> tiempo('esSubcadena3(\"abc\", \"d\"*(10**5) + \"abc\")')\n#    0.00 segundos\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Definir, por recursi\u00f3n, la funci\u00f3n esSubcadena :: String -> String -> Bool tal que esSubcadena xs ys se verifica si xs es una subcadena de ys. Por ejemplo, esSubcadena \u00abcasa\u00bb \u00abescasamente\u00bb == True esSubcadena \u00abcante\u00bb \u00abescasamente\u00bb == False esSubcadena \u00ab\u00bb \u00ab\u00bb == True Soluciones A continuaci\u00f3n se muestran las soluciones en Haskell y las soluciones…<\/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":[581],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7513"}],"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=7513"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7513\/revisions"}],"predecessor-version":[{"id":7649,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7513\/revisions\/7649"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7513"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7513"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7513"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}