Algoritmo de Knuth-Morris-Pratt en Scheme

Question

Este es el código para calcular la función de falla (cuántos pasos tenemos que retroceder) en Scheme, cuando usamos el algoritmo 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)))

Pero no entiendo la parte cuando k > 0. ¿Alguien puede explicarlo por favor?

Answer 1

Veo que está confundido con la sintaxis de un namedlet . Esta publicación hace un buen trabajo al explicar cómo funciona, pero tal vez un ejemplo con una sintaxis más familiar aclare las cosas. Tome este código en Python, agrega todos los números enteros del 1 al 10:

sum = 0
n = 1
while n <= 10:
  sum += n
  n += 1

print(sum)
=> 55

Ahora intentemos escribirlo de forma recursiva, llamaré a mi función loop. Esto es completamente equivalente:

def loop(n, sum):
    if n > 10:
        return sum
    else:
        return loop(n + 1, n + sum)

loop(1, 0)
=> 55

En el ejemplo anterior, la loopfunción implementa una iteración, el parámetro nse usa para realizar un seguimiento de la posición actual y el parámetro sumacumula la respuesta. Ahora escribamos exactamente el mismo código, pero en Scheme:

(let loop ((n 1) (sum 0))
  (cond ((> n 10) sum)
        (else (loop (+ n 1) (+ n sum)))))
=> 55

Ahora hemos definido un procedimiento local llamado loopque luego se llama automáticamente con los valores iniciales 1y 0para sus parámetros ny sum. Cuando se alcanza el caso base de la recursividad, regresamos sum, de lo contrario seguimos llamando a este procedimiento, pasando valores actualizados para los parámetros. ¡Es exactamente lo mismo que en el código Python! No se confunda con la sintaxis.

En su algoritmo, i-py kson las variables de iteración, que se inicializan en 2y 0respectivamente. Dependiendo de qué condición sea verdadera, la iteración continúa cuando volvemos a llamar loopcon valores actualizados para i-py k, o termina cuando (>= i-p n-p)se alcanza el caso , en este punto el ciclo sale y el valor calculado está en la variable sigma-table. El procedimiento finaliza devolviendo una nueva función, denominada "función de falla".