Computing the longest common subsequence length of two strings in Scheme

Question

I am trying to write a function which computes the length of the longest common subsequence of the two input strings str1 and str2. For example (LCS "scheme" "aheme") would return 4. I need some help getting started. Any ideas how to compute this?

I am also limited to the following built in function:

(read)  
(cond)  
(string-length x)  
(string-ref str x)  
(substring x y)  
(string-append x y)  
(equal? x y), (char=?)  
(remainder x y), (quotient x y)  
(max ...), (min ...)

This is what I have right now,

(define LCS
  (lambda (str1 str2)
    (if (OR (equal? str1 "") (equal? str2 ""))
        0
        (if (equal? (string-contains str1 (string-ref str2 0)) #t) 
            (+ 1 (LCS (substring str1 1 (string-length str1)) (substring str2 1 (string-length str2))))
            (LCS (substring str1 1 (string-length str1)) (substring str2 1 (string-length str2)))))))

Where string-contains returns true if a string has a certain character in it. Right now it seems like it works but I think they may be a bug.

Answer 1

Your code is totally on the right track if you don't mind a relatively slow algorithm; there's a more sophisticated approach to the problem, with dynamic programming, if you need it to be faster.

Right now, the bug in your code is that you're moving down the length of both strings simultaneously with each recursive call. It would fail, for example (I think, I haven't tried it) with the following two strings: (LCS "scheme" "emesch") Reason being is that the matching substrings don't start at the same position in the first and second string.

I suggest that you split up the recursion into two recursive calls: one where you remove a character off the front of only the first string, and one where you remove a character off the front of only the second. Then, you take the best result from either of those calls. In that fashion, you can be sure that you'll find substrings no matter where they lie in the other string.