Scheme의 Knuth-Morris-Pratt 알고리즘

Aug 18 2020

다음은 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. 누군가 제발 설명 할 수 있습니까?

답변

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

나는 당신이 명명 된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초기 값 10매개 변수 n및에 대해 자동으로 호출되는 로컬 프로 시저를 정의했습니다 sum. 재귀의 기본 케이스에 도달하면를 반환합니다 sum. 그렇지 않으면이 프로 시저를 계속 호출하여 매개 변수에 대한 업데이트 된 값을 전달합니다. 파이썬 코드에서와 똑같습니다! 구문에 혼동하지 마십시오.

알고리즘에서, i-p그리고 k초기화됩니다 반복 변수입니다 2그리고 0각각은. 조건이 참에 따라 우리가 호출 될 때 반복 계속 loop업데이트 된 값을 다시 i-p하고 k, 또는 경우에 때 끝나는 (>= i-p n-p)시점에서, 루프의 종료에 도달하고, 계산 된 값은 가변이다 sigma-table. 절차는 "실패 함수"라고하는 새 함수를 반환하여 종료됩니다.