Scheme의 Knuth-Morris-Pratt 알고리즘
다음은 Knuth-Morris-Pratt 알고리즘을 사용할 때 Scheme에서 실패 함수 (돌아 가야하는 단계 수)를 계산하는 코드입니다.
(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
. 누군가 제발 설명 할 수 있습니까?
답변
나는 당신이 명명 된let . 이 포스트 는 그것이 어떻게 작동하는지 잘 설명하고 있지만 아마도 더 친숙한 구문을 가진 예제가 일을 더 명확하게 해줄 것입니다. 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
답을 누적합니다. 이제 똑같은 코드를 작성하지만 Scheme에서 :
(let loop ((n 1) (sum 0))
(cond ((> n 10) sum)
(else (loop (+ n 1) (+ n sum)))))
=> 55
이제 우리는 loop
초기 값 1
과 0
매개 변수 n
및에 대해 자동으로 호출되는 로컬 프로 시저를 정의했습니다 sum
. 재귀의 기본 케이스에 도달하면를 반환합니다 sum
. 그렇지 않으면이 프로 시저를 계속 호출하여 매개 변수에 대한 업데이트 된 값을 전달합니다. 파이썬 코드에서와 똑같습니다! 구문에 혼동하지 마십시오.
알고리즘에서, i-p
그리고 k
초기화됩니다 반복 변수입니다 2
그리고 0
각각은. 조건이 참에 따라 우리가 호출 될 때 반복 계속 loop
업데이트 된 값을 다시 i-p
하고 k
, 또는 경우에 때 끝나는 (>= i-p n-p)
시점에서, 루프의 종료에 도달하고, 계산 된 값은 가변이다 sigma-table
. 절차는 "실패 함수"라고하는 새 함수를 반환하여 종료됩니다.