(module kmp-table (export (kmp:table Word))) (define (kmp:table Word) (let* ((WordLength (string-length Word)) (Tpref (make-vector (+ WordLength 1) 0)) ) (vector-set! Tpref 0 -1) (let loop ((i 0) (j -1) (c #a000)) ;; null character (if (>= i WordLength) Tpref (cond ((char=? c (string-ref Word i)) (vector-set! Tpref (+ i 1) (+ j 1)) (loop (+ i 1) (+ j 1) (string-ref Word (+ j 1)))) ((> j 0) (let ((j2 (vector-ref Tpref j))) (loop i j2 (string-ref Word j2)))) (else (vector-set! Tpref (+ i 1) 0) (loop (+ i 1) 0 (string-ref Word 0)))) ) )))