codepad

Language:

; 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