codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; finding digit strings in powers of two (define (string-find 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 search (let ((twos (make-vector 1000))) (do ((i 0 (+ i 1)) (t 1 (* t 2))) ((= i 1000)) (vector-set! twos i (number->string t))) (lambda (target) (let loop ((i 0)) (cond ((= i 10000) #f) ((string-find (number->string target) (vector-ref twos i)) i) (else (loop (+ i 1)))))))) (display (search 42)) (newline) (display (search 12345)) (newline)
Private
[
?
]
Run code
Submit