Algoritma Knuth-Morris-Pratt dalam Skema

Question

Ini adalah kode untuk menghitung fungsi kegagalan (berapa banyak langkah yang harus kita kembali) dalam Skema, ketika kita menggunakan algoritma 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)))

Tapi saya tidak mengerti bagian kapan k > 0. Bisakah seseorang menjelaskannya?

Answer 1

Saya melihat Anda bingung dengan sintaks bernamalet . Ini posting melakukan pekerjaan yang baik menjelaskan cara kerjanya, tapi mungkin contoh dengan sintaks lebih akrab akan membuat segalanya lebih jelas. Ambil kode ini dengan Python, ini menambahkan semua bilangan bulat dari 1 hingga 10:

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

print(sum)
=> 55

Sekarang mari kita coba menulisnya secara rekursif, saya akan memanggil fungsi saya loop. Ini sepenuhnya setara:

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

loop(1, 0)
=> 55

Dalam contoh di atas, loopfungsi mengimplementasikan iterasi, parameter ndigunakan untuk melacak posisi saat ini, dan parameter summengakumulasikan jawabannya. Sekarang mari kita tulis kode yang sama persis, tetapi dalam Skema:

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

Sekarang kita telah mendefinisikan prosedur lokal yang dipanggil loopyang kemudian secara otomatis dipanggil dengan nilai awal 1dan 0untuk parameternya ndan sum. Ketika kasus dasar rekursi tercapai, kami kembali sum, jika tidak kami terus memanggil prosedur ini, meneruskan nilai yang diperbarui untuk parameter. Ini persis sama dengan kode Python! Jangan bingung dengan sintaksnya.

Dalam algoritme Anda, i-pdan kmerupakan variabel iterasi, yang diinisialisasi ke 2dan 0masing - masing. Bergantung pada kondisi mana yang benar, iterasi berlanjut ketika kita memanggil looplagi dengan nilai yang diperbarui untuk i-pdan k, atau berakhir ketika kasus (>= i-p n-p)tercapai, pada titik ini loop keluar dan nilai yang dihitung ada di variabel sigma-table. Prosedur diakhiri dengan mengembalikan fungsi baru, yang disebut sebagai "fungsi kegagalan".