codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; 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")))
Private
[
?
]
Run code
Submit