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