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