Skip to content

Instantly share code, notes, and snippets.

@NalaGinrut
Last active December 19, 2015 08:29
Show Gist options
  • Save NalaGinrut/5925714 to your computer and use it in GitHub Desktop.
Save NalaGinrut/5925714 to your computer and use it in GitHub Desktop.
A KMP string match algorithm implementation
(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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment