; string search: knuth-morris-pratt
(define (kmp-search pat str . s)
(let* ((plen (string-length pat))
(slen (string-length str))
(skip (make-vector plen 0)))
(let loop ((i 1) (j 0))
(cond ((= i plen))
((char=? (string-ref pat i) (string-ref pat j))
(vector-set! skip i (+ j 1))
(loop (+ i 1) (+ j 1)))
((< 0 j) (loop i (vector-ref skip (- j 1))))
(else (vector-set! skip i 0)
(loop (+ i 1) j))))
(let loop ((p 0) (s (if (null? s) 0 (car s))))
(cond ((= s slen) #f)
((char=? (string-ref pat p) (string-ref str s))
(if (= p (- plen 1))
(- s plen -1)
(loop (+ p 1) (+ s 1))))
((< 0 p) (loop (vector-ref skip (- p 1)) s))
(else (loop p (+ s 1)))))))
(define-syntax assert
(syntax-rules ()
((assert expr result)
(if (not (equal? expr result))
(for-each display `(
#\newline "failed assertion:" #\newline
expr #\newline "expected: " ,result
#\newline "returned: " ,expr #\newline))))))
(define (test-search search)
(assert (search "Programming Praxis" "Programming Praxis") 0)
(assert (search "Praxis" "Programming Praxis") 12)
(assert (search "Prax" "Programming Praxis") 12)
(assert (search "praxis" "Programming Praxis") #f)
(assert (search "P" "Programming Praxis") 0)
(assert (search "P" "Programming Praxis" 5) 12)
)
(test-search kmp-search)