algorithm - Scheme中的Knuth-Morris-Pratt算法

Question

这是当我们使用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 时的部分.有人可以解释一下吗？

Answer 1

我看到您对 named let 的语法感到困惑.此 post很好地解释了它是如何工作的，但也许一个更熟悉语法的例子会让事情变得更清楚。在 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 ，否则我们继续调用这个过程，传递参数的更新值。它与 Python 代码中的完全相同!不要被语法混淆。
在您的算法中， i-p和 k是迭代变量，初始化为 2和 0分别。根据哪个条件为真，当我们调用 loop 时，迭代继续进行。再次使用 i-p 的更新值和 k , 否则结束 (>= i-p n-p)到达，此时循环退出，计算值在变量 sigma-table 中.该过程以返回一个新函数结束，称为“失败函数”。