Computing the longest common subsequence of two lists in Scheme in polynomial time

So I need to calculate the longest common subsequence of two lists, but it needs to be in polynomial time. The only problem i'm having is that I'm n开发者_如何学JAVAot allowed to use "!" at all. This means that I can't change the value of a vetcor or list using set!. I can't find a polynomial algorithm that doesn't require a 2d list or array of some sort. Anyone have any ideas?

You don't need to use set! (or any other mutating operation) to use 2d lists or vectors.

You can use the standard dynamic programming algorithm with a 2d vector, but instead of changing the vector to insert the value you calculated for a given cell, you use build-vector to create a new vector which is the same as the old one, except you changed the value at the given position.

This is highly inefficient, but still polynomial, and I don't think it's possible to do this really efficiently without laziness or mutation.

Edit: Using build-vector to do this, would look something like this:

(build-vector n (lambda (i)
  (build-vector n (lambda (j)
    (if (and (= i x) (= j y))
        new-value
        (vector-ref (vector-ref old-vector i) j))))))

Where old-vector is the n*n vector you want to copy, and you want to replace the value at position x,y with the value new-value. (Note: Using a function like this is almost always a mistake in real life because, as I said, this is quite inefficient).