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