0votos

Crear funcion de búsqueda, prefereriblemente en Python en Haskell

por josejuan hace 3 años

Una simple adaptación de la genial implementación en Haskell del algoritmo de Knuth-Morris-Pratt

Haz una función que devuelva una tabla con todas las posiciones donde encuentre una cadena.

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
-- La genial implementación del algoritmo Knuth-Morris-Pratt 
-- http://www.twanvl.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell 
data KMP a = KMP { done :: 𝔹 
                 , next :: (a → KMP a) } 
 
kmp_table :: Eq a ⇒ [a] → KMP a 
kmp_table xs = table 
  where table = mkTable xs (const table) 
        mkTable    []  failBack = KMP 𝑇 failBack 
        mkTable (x:xs) failBack = KMP 𝐹 test 
                                  where test  c = if c ≡ x then success else failBack c 
                                        success = mkTable xs $ next $ failBack x 
 
-- Con la tabla anterior sólo necesitamos saber la longitud del patrón 
data Pattern a = Pattern { patternLength    :: Int 
                         , precomputedTable :: KMP a } 
 
-- Precalcula una tabla 
precomputePattern :: Eq a ⇒ [a] → Pattern a 
precomputePattern pattern = Pattern (length pattern) (kmp_table pattern) 
 
-- Con una tabla precalculada, obtiene todas las posiciones 
kmpSearchAll' :: Eq a ⇒ Pattern a → [a] → [Int] 
kmpSearchAll' Pattern {…} = map fst ∘ filter (done ∘ snd) ∘ zip [-patternLength…] ∘ scanl next precomputedTable 
 
-- Un helper si no se usa la tabla varias veces 
kmpSearchAll :: Eq a ⇒ [a] → [a] → [Int] 
kmpSearchAll pattern = kmpSearchAll' (precomputePattern pattern) 
1 comentario

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.