Algorithme de Knuth-Morris-Pratt dans Scheme
C'est le code pour calculer la fonction d'échec (combien d'étapes nous devons reculer) dans Scheme, lorsque nous utilisons l'algorithme de Knuth-Morris-Pratt:
(define (compute-failure-function p)
(define n-p (string-length p))
(define sigma-table (make-vector n-p 0))
(let loop
((i-p 2)
(k 0))
(cond
((>= i-p n-p)
(vector-set! sigma-table (- n-p 1) k))
((eq? (string-ref p k)
(string-ref p (- i-p 1)))
(vector-set! sigma-table i-p (+ k 1))
(loop (+ i-p 1) (+ k 1)))
((> k 0)
(loop i-p (vector-ref sigma-table k)))
(else ; k=0
(vector-set! sigma-table i-p 0)
(loop (+ i-p 1) k))))
(vector-set! sigma-table 0 -1)
(lambda (q)
(vector-ref sigma-table q)))
Mais je ne comprends pas la partie quand k > 0
. Quelqu'un peut-il l'expliquer s'il vous plaît?
Réponses
Je vois que vous êtes confus avec la syntaxe d'un namedlet . Cet article explique bien son fonctionnement, mais peut-être qu'un exemple avec une syntaxe plus familière rendra les choses plus claires. Prenez ce code en Python, il ajoute tous les entiers de 1 à 10:
sum = 0
n = 1
while n <= 10:
sum += n
n += 1
print(sum)
=> 55
Essayons maintenant de l'écrire de manière récursive, j'appellerai ma fonction loop
. C'est tout à fait équivalent:
def loop(n, sum):
if n > 10:
return sum
else:
return loop(n + 1, n + sum)
loop(1, 0)
=> 55
Dans l'exemple ci-dessus, la loop
fonction implémente une itération, le paramètre n
est utilisé pour garder une trace de la position actuelle et le paramètre sum
accumule la réponse. Maintenant, écrivons exactement le même code, mais dans Scheme:
(let loop ((n 1) (sum 0))
(cond ((> n 10) sum)
(else (loop (+ n 1) (+ n sum)))))
=> 55
Nous avons maintenant défini une procédure locale appelée loop
qui est ensuite automatiquement appelée avec les valeurs initiales 1
et 0
pour ses paramètres n
et sum
. Lorsque le cas de base de la récursion est atteint, nous retournons sum
, sinon nous continuons d'appeler cette procédure, en passant des valeurs mises à jour pour les paramètres. C'est exactement la même chose que dans le code Python! Ne soyez pas confus par la syntaxe.
Dans votre algorithme, i-p
et k
sont les variables d'itération, qui sont respectivement initialisées à 2
et 0
. Selon la condition vraie, l'itération continue lorsque nous appelons à loop
nouveau avec des valeurs mises à jour pour i-p
et k
, ou elle se termine lorsque le cas (>= i-p n-p)
est atteint, à ce stade, la boucle se termine et la valeur calculée est dans la variable sigma-table
. La procédure se termine par le retour d'une nouvelle fonction, appelée «fonction d'échec».