Knuth-Morris-Pratt en style récursif - [Site WWW de Laurent Bloch]

Retour sur la recherche de mots dans un texte :

Knuth-Morris-Pratt en style récursif

Article mis en ligne le 13 mai 2008

dernière modification le 9 juin 2013

Voici comme promis une version en style récursif du programme Knuth-Morris-Pratt. Ce type d’exercice est plein de pièges : si vous découvrez que je suis tombé dans l’un d’entre eux, je serais content que vous me le signaliez.

(module kmp-table
   (export (kmp:table Word)))

(define (kmp:table Word)
   (let* ((WordLength (string-length Word))
          (Tpref (make-vector (+ WordLength 1) 0)) )
      (vector-set! Tpref 0 -1)
      (let loop ((i 0)
                 (j -1)
                 (c #a000))    ;;  null character
         (if (>= i WordLength)
             Tpref
             (cond ((char=? c (string-ref Word i))
                    (vector-set! Tpref (+ i 1) (+ j 1))
                    (loop (+ i 1)
                          (+ j 1)
                          (string-ref Word (+ j 1))))
                   ((> j 0)
                    (let ((j2 (vector-ref Tpref j)))
                       (loop i
                             j2
                             (string-ref Word j2))))
                   (else
                    (vector-set! Tpref (+ i 1) 0)
                    (loop (+ i 1)
                          0
                          (string-ref Word 0)))) ) )))

(module kmp
   (main main)
   (import kmp-table))

(define (main args)
   (print (kmp:KMP (cadr args) (caddr args))))

(define (kmp:KMP Word Text)
   (let ((Tpref (kmp:table Word))
         (L-texte (string-length Text))
         (LastCharPos (- (string-length Word) 1)))
      (let loop ((m 0)         ;; match
                 (i 0))        ;; index
         (cond ((>= (+ m i) L-texte)
                -1)
               ((char=? (string-ref Text (+ m i))
                        (string-ref Word i))
                (if (= i LastCharPos)
                    m
                    (loop m (+ i 1))))
               (else
                (loop
                 (- (+ m i) (vector-ref Tpref i))
                 (if (> i 0)
                     (vector-ref Tpref i)
                     i))) ) ) ))

Dans la même rubrique

Votre inscription a été enregistrée avec succès !

Au menu

Dans la même rubrique