Reconocimiento de subcadenas
Definir, por recursión, la función
|
1 |
esSubcadena :: String -> String -> Bool |
tal que esSubcadena xs ys se verifica si xs es una subcadena de ys. Por ejemplo,
|
1 2 3 |
esSubcadena "casa" "escasamente" == True esSubcadena "cante" "escasamente" == False esSubcadena "" "" == True |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
-- 1ª solución -- =========== esSubcadena1 :: String -> String -> Bool esSubcadena1 [] _ = True esSubcadena1 _ [] = False esSubcadena1 xs (y:ys) = xs `isPrefixOf` (y:ys) || xs `esSubcadena1` ys -- 2ª solución -- =========== esSubcadena2 :: String -> String -> Bool esSubcadena2 xs ys = or [xs `isPrefixOf` zs | zs <- sufijos ys] -- (sufijos xs) es la lista de sufijos de xs. Por ejemplo, -- sufijos "abc" == ["abc","bc","c",""] sufijos :: String -> [String] sufijos xs = [drop i xs | i <- [0..length xs]] -- 3ª solución -- =========== esSubcadena3 :: String -> String -> Bool esSubcadena3 xs ys = or [xs `isPrefixOf` zs | zs <- tails ys] -- 4ª solución -- =========== esSubcadena4 :: String -> String -> Bool esSubcadena4 xs ys = any (xs `isPrefixOf`) (tails ys) -- 5ª solución -- =========== esSubcadena5 :: String -> String -> Bool esSubcadena5 = (. tails) . any . isPrefixOf -- 6ª solución -- =========== esSubcadena6 :: String -> String -> Bool esSubcadena6 = isInfixOf -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_esSubcadena :: String -> String -> Bool prop_esSubcadena xs ys = all (== esSubcadena1 xs ys) [esSubcadena2 xs ys, esSubcadena3 xs ys, esSubcadena4 xs ys, esSubcadena5 xs ys, esSubcadena6 xs ys] -- La comprobación es -- λ> quickCheck prop_esSubcadena -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> esSubcadena1 "abc" (replicate (5*10^4) 'd' ++ "abc") -- True -- (0.03 secs, 17,789,392 bytes) -- λ> esSubcadena2 "abc" (replicate (5*10^4) 'd' ++ "abc") -- True -- (6.32 secs, 24,989,912 bytes) -- -- λ> esSubcadena1 "abc" (replicate (5*10^6) 'd' ++ "abc") -- True -- (3.24 secs, 1,720,589,432 bytes) -- λ> esSubcadena3 "abc" (replicate (5*10^6) 'd' ++ "abc") -- True -- (1.81 secs, 1,720,589,656 bytes) -- λ> esSubcadena4 "abc" (replicate (5*10^6) 'd' ++ "abc") -- True -- (0.71 secs, 1,120,589,480 bytes) -- λ> esSubcadena5 "abc" (replicate (5*10^6) 'd' ++ "abc") -- True -- (0.41 secs, 1,120,589,584 bytes) -- λ> esSubcadena6 "abc" (replicate (5*10^6) 'd' ++ "abc") -- True -- (0.11 secs, 560,589,200 bytes) |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
from sys import setrecursionlimit from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st setrecursionlimit(10**6) # 1ª solución # =========== def esSubcadena1(xs: str, ys: str) -> bool: if not xs: return True if not ys: return False return ys.startswith(xs) or esSubcadena1(xs, ys[1:]) # 2ª solución # =========== # sufijos(xs) es la lista de sufijos de xs. Por ejemplo, # sufijos("abc") == ['abc', 'bc', 'c', ''] def sufijos(xs: str) -> list[str]: return [xs[i:] for i in range(len(xs) + 1)] def esSubcadena2(xs: str, ys: str) -> bool: return any(zs.startswith(xs) for zs in sufijos(ys)) # 3ª solución # =========== def esSubcadena3(xs: str, ys: str) -> bool: return xs in ys # Comprobación de equivalencia # ============================ # La propiedad es @given(st.text(), st.text()) def test_esSubcadena(xs: str, ys: str) -> None: r = esSubcadena1(xs, ys) assert esSubcadena2(xs, ys) == r assert esSubcadena3(xs, ys) == r # La comprobación es # src> poetry run pytest -q reconocimiento_de_subcadenas.py # 1 passed in 0.35s # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('esSubcadena1("abc", "d"*(10**4) + "abc")') # 0.02 segundos # >>> tiempo('esSubcadena2("abc", "d"*(10**4) + "abc")') # 0.01 segundos # >>> tiempo('esSubcadena3("abc", "d"*(10**4) + "abc")') # 0.00 segundos # # >>> tiempo('esSubcadena2("abc", "d"*(10**5) + "abc")') # 1.74 segundos # >>> tiempo('esSubcadena3("abc", "d"*(10**5) + "abc")') # 0.00 segundos |