27 lines
673 B
Racket
27 lines
673 B
Racket
#lang racket
|
|
(define (longest xs ys)
|
|
(if (> (length xs) (length ys))
|
|
xs ys))
|
|
|
|
(define memo (make-hash))
|
|
(define (lookup xs ys)
|
|
(hash-ref memo (cons xs ys) #f))
|
|
(define (store xs ys r)
|
|
(hash-set! memo (cons xs ys) r)
|
|
r)
|
|
|
|
(define (lcs/list sx sy)
|
|
(or (lookup sx sy)
|
|
(store sx sy
|
|
(match* (sx sy)
|
|
[((cons x xs) (cons y ys))
|
|
(if (equal? x y)
|
|
(cons x (lcs/list xs ys))
|
|
(longest (lcs/list sx ys) (lcs/list xs sy)))]
|
|
[(_ _) '()]))))
|
|
|
|
(define (lcs sx sy)
|
|
(list->string (lcs/list (string->list sx) (string->list sy))))
|
|
|
|
(lcs "thisisatest" "testing123testing")
|