Longest Common Subsequence
  
  Why do you care? (checker output overhead)
  Also note use of tokens, not pure strings.
  
  This is a very practical problem: RCS, SCSS, diff, moss, checker.  Can
  work at the line (diff), character (RCS, SCSS), or token (moss,
  checker) level.  Also the genome project, DNA sequencing, genetically
  engineered plants, etc.  Also lawsuits over music plagiarism....
  
  moss and checker are two algorithms to quantify
  programsimilarity using LCS's of tokens.
  
  The Longest common subsequence (LCS) is lines (tokens, etc) that have
  NOT been changed.  Often its complement (diff, RCS) is what's interesting,
  but often otherwise (checker, moss).
  
  The ADT here is sequence, but we can use a data model of list for our
  implementations. 
  
  recall a subsequence U of sequence S is created from S by deleting
  members, so
  
  fornication
  is a subsequence of 
  california vacation
  
  Puzzle:
  On a highway you see a common 3-letter abbreviation.  If you
  intersperse 5 other letters among the letters (in order) of the
  abbreviation, you get a 2nd (8-letter) word.  But those 5 letters, in
  the order you interspersed them, form a third word.  AND all three
  (abbrev, 2 words) mean the same thing(!).  What are the words and
  abbreviation?
  
  Clearly the abbrev and the 5-letter words are subsequences of the
  8-letter  word, since order is preserved in all the words and
  abbreviations of the puzzle.
  
  
  ---------
  LCS is the longest common subsequence between two sequences.
  
  How to find these LCS's?
  
  We find the length of the LCS's of all prefixes of the two
  sequences... the longest prefix is the sequence itself so we
  eventually work up to the answer.  Further we save all these lengths
  in a table and from that we can compute the LCS itself.
  
  These two characteristics, working from one end to the other of a
  problem, solving the next step in terms of the previous solution, and
  keeping the results in a table, are reliable signs that Dynamic
  Programming (DP) is or should be involved.
  
  Toy example:
  
  Recursive Fibonacci:
   rabbit populations, various natural phenomena
  F(0) = F(1) = 1; // easy to see how to make this into a program.  F(n)
  = F(n-1) + F(n-2); notice to compute F(6) you're going to compute F(4)
  twice, once to get F(6) and once to get F(5).  Think how often you're
  going to compute F(2)!
  
  Recurrence is T(n) = O(1)  +  T(n-1) + T(n-2), which makes
  T(n) exponential.
  
  But this is a stupid way to do Fib in real life.  Actually you compute
  it in the other direction, using results already generated and kept in
  a ``table''.  Here our ``table'' is simply the two variables Last and
  Next_To_Last, which if we wanted to we could keep in Table[0] and
  Table[1]....If Fib(N) depended on lots of the values of F(N-n), then
  we might want to keep around the N-long table of all Fibonacci
  numbers.  That approach is what we use in DP for LCS in fact.
  
  int Fib (const unsigned int N)
  {
  unsigned int Last = 1, Next_to_Last = 1, Answer;
  
  if (N <= 1) return 1;  //by convention
  
  for (int i = 2; i<=N i++)
   {
     Answer = Last + Next_to_Last;  // new answer
     Next_to_Last = Last;           // update table
     Last = Answer;
    }
    return Answer;
  }
  
  And this only computes things once. Another good example is
  Pascal's triangle for computing the binomial coefficients (FCS
  p. 172).
  
  Details in FCS p.p 323-326, along with C algorithm.
  
  To compute LCS length from prefixes:
  
  (a1,...,ai) and (b1,...,bj)
  
  If ai != bj, the match can't include both ai and bj. Thus their LCS
  must be either
     the LCS of (a1,...,a[i-1]) and (b1,...,bj) or
     the LCS of (a1,...,ai) and (b1,...,b[j-1])
  So if we know these lengths, the larger is the right answer.
  
  if ai = bj, we can match the two and that won't interfere with other
  matches in the future, so length of LCS is 1 greater than the length
  of the LCS of the two argument prefixes.
  
  These observations are turned into a recursion on p. 323 and a program
  on p. 324.  What is neat about this is that we use previous prefix
  computations (kept in a table) to compute the new answer...we can just
  look them up, as in Fib.
  
  ------
  Resulting Length Table:
  
  DP often gives answer out in the form of a table that must be
  interpreted.  Like it gives the lengths of the sequences but not the
  sequences themselves, or the lengths of paths but not the places the
  paths go through.  So for example for cbab and abca, have table giving
  LCS of prefixes of length shown
  
  b 4 |  0  1  2  2  2
  a 3 |  0  1  1  1  2
  b 2 |  0  0  1  1  1
  c 1 |  0  0  0  1  1
    0 |  0  0  0  0  0
  -------------------
         0  1  2  3  4
            a  b  c  a
  
  
  So there are LCSs of length 2 in these sequences, we know that.  Pick
  one, say the upper right.  If it's row and column letters match, then
  its prefix must have LCS of length one less.  So move down and left in
  the table by one and emit the matching r and c as the last char in the
  LCS.  If its r and c do not match, then you have to be able to toss
  out the last character in one sequence or the other and preserve the
  LCS length.  That means you have to have a 2 either just to left or
  down.  In this case we have both, indicating two choices for matching
  subsequences of length two (at least -- two already at this stage).
  Repeat this reasoning.  So if you do that you get lots of paths in
  this case: here are a couple...
  
  
  b 4 |              2
  a 3 |              2   emit a
  b 2 |        1  1      emit b
  c 1 |     0                   this finds LCS ba
    0 |  0   
  -------------------
         0  1  2  3  4
            a  b  c  a
  
  
  b 4 |              2
  a 3 |              2   emit a
  b 2 |           1  
  c 1 |           1      emit c 
    0 |        0                   this finds LCS ca
  -------------------
         0  1  2  3  4
            a  b  c  a
  
  
  Note throughout this book that inductive proofs are used to establish
  correctness of algorithms!
  
  -----------
  
  Added in proof...notes about LCS.  Pseudocode..
  
  The recursive definition of the LCS algorithm from the book:
  This would be easy to translate into a recursive program, same as
  Fibonacci or Pascal's Triangle would be.
  
  L(0,0) = 0.
  
  Consider i and j, and suppose we've already computed L(g,h) for any g
  and h such that g+h < i+j.  // this basically says you have all
  shorter solutions from 0 on up....like computing everything to the
  left and below in the table.
  
  
    if i or j = 0, L(i,j) = 0.
    if i,j >0, ai != bj,  L(i,j) = max (L(i, j-1),  L(i-1,j)). // very  DP
    if i,j >0, ai = bj,  L(i,j) = 1 + (L(i-1, j-1)
  
  Above, L(i,j) is a RECURSIVE  CALL.
  
  So the iterative version of this (Fig. 6.31) is basically
  
  store x in a[1,m], y in b[1,n]... use 0th elements to store zeroes
  ``around theoutside'' for trivial cases...
  
  
  Below, L[i,j] is an ARRAY LOOKUP.
  
    //initialize first
  
   set first row and first col. to 0s
  
  
  for i = 1 to m
    for j = 1 to n
      if ai != bi
          if L[i-1,j] >= L[i, j-1]
             L[i,j] = L[i-1,j]
          else
             L[i,j] = L[i,j-1]  // no match, so the answer so far
                                // is the biggest of these two (smaller)
                                //prefix matches
       else                     //a match!! we've discovered 1-longer ans.
             L[i,j] = 1+ L[i-1,j-1]