Алгоритм Кнута-Морриса-Пратта в схеме

Aug 18 2020

Это код для вычисления функции отказа (на сколько шагов нам нужно вернуться) в схеме, когда мы используем алгоритм Кнута-Морриса-Пратта:

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

Но я не понимаю, с какой стороны k > 0. Может кто-нибудь объяснить это, пожалуйста?

Ответы

2 ÓscarLópez Aug 18 2020 at 22:54

Я вижу, вы запутались с синтаксисом файла namedlet . В этом посте хорошо объясняется, как это работает, но, возможно, пример с более знакомым синтаксисом прояснит ситуацию. Возьмите этот код на Python, он складывает все целые числа от 1 до 10:

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

print(sum)
=> 55

Теперь попробуем записать это рекурсивно, я вызову свою функцию loop. Это полностью эквивалентно:

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

loop(1, 0)
=> 55

В приведенном выше примере loopфункция реализует итерацию, параметр nиспользуется для отслеживания текущей позиции, а параметр sumнакапливает ответ. Теперь напишем точно такой же код, но на схеме:

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

Теперь мы определили локальную процедуру , называемую loopкоторая затем автоматически вызывается с начальными значениями 1и 0для его параметров nи sum. Когда достигается базовый вариант рекурсии, мы возвращаемся sum, в противном случае мы продолжаем вызывать эту процедуру, передавая обновленные значения для параметров. Точно так же, как в коде Python! Пусть вас не смущает синтаксис.

В вашем алгоритме i-pи k- переменные итерации, которые инициализируются значениями 2и 0соответственно. В зависимости от того, какое условие истинно, итерация продолжается, когда мы loopснова вызываем обновленные значения для i-pи k, или она заканчивается, когда (>= i-p n-p)достигается случай , в этот момент цикл завершается, и вычисленное значение находится в переменной sigma-table. Процедура заканчивается возвратом новой функции, называемой «функцией отказа».