; longest common subsequence
(define (make-matrix rows columns)
(do ((m (make-vector rows)) (i 0 (+ i 1)))
((= i rows) m)
(vector-set! m i (make-vector columns))))
(define (matrix-rows x) (vector-length x))
(define (matrix-cols x) (vector-length (vector-ref x 0)))
(define (matrix-ref m i j) (vector-ref (vector-ref m i) j))
(define (matrix-set! m i j x) (vector-set! (vector-ref m i) j x))
(define-syntax for
(syntax-rules ()
((for (var first past step) body ...)
(let ((ge? (if (< first past) >= <=)))
(do ((var first (+ var step)))
((ge? var past))
body ...)))
((for (var first past) body ...)
(let* ((f first) (p past) (s (if (< first past) 1 -1)))
(for (var f p s) body ...)))
((for (var past) body ...)
(let* ((p past)) (for (var 0 p) body ...)))))
(define (lcs eql? xs ys)
(let* ((x-len (length xs)) (y-len (length ys))
(x1 (+ x-len 1)) (y1 (+ y-len 1))
(xv (list->vector xs)) (yv (list->vector ys))
(m (make-matrix x1 y1)))
(for (x 0 x1)
(for (y 0 y1)
(cond ((or (zero? x) (zero? y))
(matrix-set! m x y 0))
((eql? (vector-ref xv (- x 1))
(vector-ref yv (- y 1)))
(matrix-set! m x y
(+ 1 (matrix-ref m (- x 1) (- y 1)))))
(else (matrix-set! m x y
(max (matrix-ref m (- x 1) y)
(matrix-ref m x (- y 1))))))))
(let loop ((x x-len) (y y-len) (zs '()))
(cond ((or (zero? x) (zero? y)) zs)
((= (matrix-ref m x y) (matrix-ref m (- x 1) y))
(loop (- x 1) y zs))
((= (matrix-ref m x y) (matrix-ref m x (- y 1)))
(loop x (- y 1) zs))
(else (loop (- x 1) (- y 1) (cons (vector-ref xv (- x 1)) zs)))))))
(display (lcs char=? (string->list "PROGRAMMING") (string->list "PRAXIS")))