Algorytm Knutha-Morrisa-Pratta w schemacie

Question

Oto kod do obliczenia funkcji błędu (ile kroków musimy cofnąć) w Scheme, gdy używamy algorytmu Knutha-Morrisa-Pratta:

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

Ale nie rozumiem części, kiedy k > 0. Czy ktoś może to wyjaśnić?

Answer 1

Widzę, że jesteś zdezorientowany ze składnią nazwanegolet . Ten post dobrze się spisuje, wyjaśniając, jak to działa, ale być może przykład z bardziej znaną składnią wyjaśni sprawę. Weź ten kod w Pythonie, dodaje on wszystkie liczby całkowite od 1 do 10:

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

print(sum)
=> 55

Teraz spróbujmy zapisać to w sposób rekurencyjny, wywołam moją funkcję loop. To jest całkowicie równoważne:

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

loop(1, 0)
=> 55

W powyższym przykładzie loopfunkcja implementuje iterację, parametr nsłuży do śledzenia aktualnej pozycji, a parametr sumgromadzi odpowiedź. Teraz napiszmy dokładnie ten sam kod, ale w Schemacie:

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

Teraz zdefiniowaliśmy lokalną procedurę o nazwie, loopktóra jest następnie automatycznie wywoływana z wartościami początkowymi 1i 0parametrami noraz sum. Po osiągnięciu podstawowego przypadku rekursji zwracamy sum, w przeciwnym razie nadal wywołujemy tę procedurę, przekazując zaktualizowane wartości parametrów. To dokładnie to samo, co w kodzie Pythona! Nie daj się zmylić składnią.

W twoim algorytmie i-pi ksą zmienne iteracji, które są inicjalizowane odpowiednio do 2i 0. W zależności od tego, który warunek jest prawdziwy, iteracja jest kontynuowana, gdy loopponownie wywołujemy ze zaktualizowanymi wartościami dla i-pi k, lub kończy się po osiągnięciu przypadku (>= i-p n-p), w tym momencie pętla kończy się, a obliczona wartość znajduje się w zmiennej sigma-table. Procedura kończy się zwróceniem nowej funkcji, zwanej „funkcją niepowodzenia”.