Алгоритм Кнута-Морриса-Пратта в схеме
Это код для вычисления функции отказа (на сколько шагов нам нужно вернуться) в схеме, когда мы используем алгоритм Кнута-Морриса-Пратта:
(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
. Может кто-нибудь объяснить это, пожалуйста?
Ответы
Я вижу, вы запутались с синтаксисом файла 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
. Процедура заканчивается возвратом новой функции, называемой «функцией отказа».