Algoritmo di Knuth-Morris-Pratt in Scheme
Questo è il codice per calcolare la funzione di guasto (quanti passaggi dobbiamo tornare indietro) in Scheme, quando usiamo l'algoritmo di 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)))
Ma non capisco la parte in cui k > 0
. Qualcuno può spiegarlo per favore?
Risposte
Vedo che sei confuso con la sintassi di un namedlet . Questo post spiega come funziona, ma forse un esempio con una sintassi più familiare renderà le cose più chiare. Prendi questo codice in Python, aggiunge tutti i numeri interi da 1 a 10:
sum = 0
n = 1
while n <= 10:
sum += n
n += 1
print(sum)
=> 55
Ora proviamo a scriverlo in modo ricorsivo, chiamerò la mia funzione loop
. Questo è completamente equivalente:
def loop(n, sum):
if n > 10:
return sum
else:
return loop(n + 1, n + sum)
loop(1, 0)
=> 55
Nell'esempio precedente, la loop
funzione implementa un'iterazione, il parametro n
viene utilizzato per tenere traccia della posizione corrente e il parametro sum
accumula la risposta. Ora scriviamo lo stesso identico codice, ma in Scheme:
(let loop ((n 1) (sum 0))
(cond ((> n 10) sum)
(else (loop (+ n 1) (+ n sum)))))
=> 55
Ora abbiamo definito una procedura locale chiamata loop
che viene poi chiamata automaticamente con i valori iniziali 1
e 0
per i suoi parametri n
e sum
. Quando viene raggiunto il caso base della ricorsione, torniamo sum
, altrimenti continuiamo a chiamare questa procedura, passando i valori aggiornati per i parametri. È esattamente lo stesso del codice Python! Non lasciarti confondere dalla sintassi.
Nel tuo algoritmo, i-p
e k
sono le variabili di iterazione, che sono inizializzate rispettivamente a 2
e 0
. A seconda di quale condizione è vera, l'iterazione continua quando chiamiamo di loop
nuovo con valori aggiornati per i-p
e k
, oppure termina quando (>= i-p n-p)
viene raggiunto il caso , a questo punto il ciclo termina e il valore calcolato è nella variabile sigma-table
. La procedura termina restituendo una nuova funzione, denominata "funzione di errore".