codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; 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)
Private
[
?
]
Run code
Submit