A KMP string match algorithm implementation

kmp.scm

(use-modules (srfi srfi-1) (ice-9 receiver))

(define (gen-xfix-list str generator)
  (let lp((ret '()) (n (1- (string-length str))))
    (if (zero? n) ret (lp (cons (generator str n) ret) (1- n)))))

(define (gen-prefix-list str)
  (gen-xfix-list str (lambda (str n) (substring str 0 n))))

(define (gen-suffix-list str)
  (gen-xfix-list str (lambda (str n) (substring str n))))

(define (count-partial-matches str)
  (and (string-null? str) (error count-partial-matches "it's null string"))
  (receiver (p s) (values (gen-prefix-list str) (gen-suffix-list str))
            (length (lset-intersection string=? prefix suffix))))

(define (kmp str what)
  (let ((len-str (string-length str)) (len-what (string-length what)))
  (and (< len-str len-what) (error "impossible has match"))
  (let lp((i 0) (j 0))
    (cond
     ((> i len-str) #f) ; no match at all
     ((char=? (string-ref str i) (string-ref what j))
      (if (= j (1- len-what)) (values (- i j) (1+ i)) #; all-matches (lp (1+ i) (1+ j)))) ; keep on searching
     ((= j 0) (lp (1+ i) j)) ; no match char
     (else (lp (+ i (- j (count-partial-matches (substring what 0 j)))) 0)))))); move to new index