Talk:Algorithm Implementation/Strings/Longest common subsequence

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search

Contents

[edit] Error in the section "C# - Reading the LCS

I think there is an error in this section, because if s1position and/or s2position are exactly zero, and the corresponding char in string1 doesn't match the char in string2, then the algorithm will try to access a negative index in the backtrack array which should result in an indexOutOfBounds exception.

Therefore I would suggest to add the condition below after the

   else if (string1[s1position] == string2[s2posision]) {...}

statement:

   else if ((s1position == 0) || (s2posision == 0)) {
       return new StringBuilder();
   }

Additionally "s2posision" should probably renamed to "s2position" to be more meaningful. --87.95.15.51 (talk) 17:37, 28 July 2009 (UTC)


[edit] Are the null checks in the Java implementation necessary and correct?

It's not obvious that the null checks in the Java implementation here are necessary or correct:

   protected boolean equals(VALUE x1, VALUE y1) {
       return (null == x1 && null == y1) || x1.equals(y1);
   }

If x1 can be null when y1 is non-null, then x1.equals(y1) can throw a NullPointerException and a test like this should be used instead:

   protected boolean equals(VALUE x1, VALUE y1) {
       return x1 != null ? x1.equals(y1) : y1 == null;
   }

If x1 can be null only when y1 is also null, then the code is ok but a comment would be appropriate because that's not obvious.

If neither should be null, then the null checks should be removed since they could cover up a coding error, and equals shouldn't be quietly accepting invalid arguments.
Atomota 23:09, 22 November 2007 (UTC)

[edit] Redundant assignment in LongestCommonSubsequence.backtrack()

This has no effective impact on the algorithm implementation, but the following line in the LongestCommonSubsequence.backtrack() method:

   this.backtrack = backtrack = new ArrayList<VALUE>();

could be simplified. The middle term is redundant, resulting in:

   this.backtrack = new ArrayList<VALUE>();

(I noticed this when Eclipse pointed it out to me.)

[edit] C++ example allocating a 2-D array

For the C++ example I deliberately left out the code for creating a 2-D array to keep things simple, and because everyone has a different way they like to do this. Here is one possible way to create a 2-D array that matches the example code:

template < typename T >
T **Allocate2DArray( int nRows, int nCols)
{
  T **ppi;
  T *pool;
  T *curPtr;
  //(step 1) allocate memory for array of elements of column

  ppi = new T*[nRows];

  //(step 2) allocate memory for array of elements of each row
  pool = new T [nRows * nCols];

  // Now point the pointers in the right place
  curPtr = pool;
  for( int i = 0; i < nRows; i++)
  {
    *(ppi + i) = curPtr;
    curPtr += nCols;
  }
  return ppi;
}

template < typename T >
void Free2DArray(T** Array)
{
  delete [] *Array;
  delete [] Array;
}
Retrieved from "http://en.wikibooks.org/wiki/Talk:Algorithm_Implementation/Strings/Longest_common_subsequence"