Algoritmo Knuth-Morris-Pratt no Esquema

Question

Este é o código para calcular a função de falha (quantas etapas temos que voltar) no Scheme, quando usamos o 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)))

Mas eu não entendo a parte quando k > 0. Alguém pode explicar por favor?

Answer 1

Vejo que você está confuso com a sintaxe de um nomelet . Esta postagem explica como funciona, mas talvez um exemplo com uma sintaxe mais familiar torne as coisas mais claras. Pegue este código em Python, ele adiciona todos os inteiros de 1 a 10:

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

print(sum)
=> 55

Agora vamos tentar escrever de forma recursiva, vou chamar minha função loop. Isso é completamente equivalente:

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

loop(1, 0)
=> 55

No exemplo acima, a loopfunção implementa uma iteração, o parâmetro né usado para rastrear a posição atual e o parâmetro sumacumula a resposta. Agora vamos escrever exatamente o mesmo código, mas em Scheme:

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

Agora definimos um procedimento local chamado loopque é automaticamente chamado com os valores iniciais 1e 0para seus parâmetros ne sum. Quando o caso base da recursão é alcançado, retornamos sum, caso contrário, continuamos chamando este procedimento, passando valores atualizados para os parâmetros. É exatamente igual ao código Python! Não se confunda com a sintaxe.

Em seu algoritmo, i-pe ksão as variáveis ​​de iteração, que são inicializadas com 2e 0respectivamente. Dependendo de qual condição é verdadeira, a iteração continua quando chamamos loopnovamente com valores atualizados para i-pe k, ou termina quando o caso (>= i-p n-p)é alcançado, neste ponto o loop sai e o valor calculado está na variável sigma-table. O procedimento termina com o retorno de uma nova função, denominada "função de falha".