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))) ) ) ))