; string-replace
; replace all occurrences of pat in str with rep

(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 (string-replace str pat rep) ; quadratic
  (let ((x (string-find pat str)))
    (if (not x) str
      (string-append (substring str 0 x) rep
        (string-replace (substring str (+ x (string-length pat))
          (string-length str)) pat rep)))))

(time (begin (string-replace (make-string 1000 #\a) "a" "b") 'done))

(define (string-replace str pat rep) ; linear
  (let ((str-len (string-length str))
        (pat-len (string-length pat)))
    (let loop ((pos 0) (xs (list)))
      (if (<= str-len pos)
          (apply string-append (reverse xs))
          (let ((x (string-find pat str pos)))
            (if x
                (loop (+ pos pat-len)
                      (cons rep (cons (substring str pos x) xs)))
                (loop str-len (cons (substring str pos str-len) xs))))))))

(time (begin (string-replace (make-string 1000 #\a) "a" "b") 'done))