[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/MQK6CN9q    [ raw code | output | fork ]

Scheme, pasted on May 28:
; 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")))


Output:
1
(P R A I)


Create a new paste based on this one


Comments: