; string-search: boyer-moore

(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)
)

(define (bm-search pat str . s)
  (define (ord str s) (char->integer (string-ref str s)))
  (let* ((plen (string-length pat))
         (slen (string-length str))
         (skip (make-vector 256 plen)))
    (do ((p 0 (+ p 1))) ((= p plen))
      (vector-set! skip (ord pat p) (- plen p 1)))
    (let loop ((p (- plen 1)) (s (if (null? s) (- plen 1) (+ (car s) plen -1))))
      (cond ((negative? p) (+ s 1))
            ((<= slen s) #f)
            ((char=? (string-ref pat p) (string-ref str s)) (loop (- p 1) (- s 1)))
            (else (loop (- plen 1) (+ s (vector-ref skip (ord str s)))))))))

(test-search bm-search)