Scheme'de Knuth-Morris-Pratt algoritması

Question

Bu, Knuth-Morris-Pratt algoritmasını kullandığımızda Scheme'deki hata fonksiyonunu (kaç adım geri gitmemiz gerektiğini) hesaplamak için kullanılan koddur:

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

Ama ne zaman olduğunu anlamıyorum k > 0. Lütfen birisi açıklayabilir mi?

Answer 1

Görüyorum ki bir isimlilet sözdizimiyle karıştırmışsın . Bu gönderi , nasıl çalıştığını açıklamak için iyi bir iş çıkarıyor, ancak belki daha tanıdık sözdizimine sahip bir örnek, işleri daha net hale getirecektir. Bu kodu Python'da alın, 1'den 10'a kadar tüm tam sayıları ekler:

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

print(sum)
=> 55

Şimdi bunu yinelemeli bir şekilde yazmaya çalışalım, ben fonksiyonumu arayacağım loop. Bu tamamen eşdeğerdir:

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

loop(1, 0)
=> 55

Yukarıdaki örnekte, loopişlev bir yineleme uygular, parametre ngeçerli konumu takip etmek için kullanılır ve parametre sumyanıtı toplar. Şimdi tam olarak aynı kodu yazalım, ancak Scheme'de:

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

Şimdi denilen yerel bir prosedür tanımladığınız loopsonra otomatik olarak başlangıç değerleriyle denir 1ve 0onun parametreleri için nve sum. Özyinelemenin temel durumuna ulaşıldığında, geri döneriz sum, aksi takdirde bu prosedürü çağırmaya devam ederiz, parametreler için güncellenmiş değerleri iletiriz. Python kodundaki ile tamamen aynı! Sözdizimi ile kafanızı karıştırmayın.

Senin algoritmasında, i-pve kbaşlatılır yineleme değişkenler vardır 2ve 0sırasıyla. Koşul doğru olduğu bağlı olarak, çağırdığınızda yineleme devam loopiçin güncellenmiş değerlerle tekrar i-pve kya dava zaman biter (>= i-p n-p)bu noktada döngü çıkar ulaşıldığında ve hesaplanan değer değişkeni olduğunu sigma-table. Prosedür, "başarısızlık işlevi" olarak adlandırılan yeni bir işlevi döndürerek sona erer.