list::longestCommonSubsequence

 list::longestCommonSubsequence

Defined in

Partial Call Graph (max 5 caller/called nodes):

Testcases:

No testcase defined.

Source code:

  set seta [list]
  set setb [list]

  # Construct a set of equivalence classes of lines in file 2

  set index 0
  foreach string $sequence2 {
    lappend eqv($string) $index
    incr index
  }

  # K holds descriptions of the common subsequences.
  # Initially, there is one common subsequence of length 0,
  # with a fence saying that it includes line -1 of both files.
  # The maximum subsequence length is 0; position 0 of
  # K holds a fence carrying the line following the end
  # of both files.

  lappend K [list -1 -1 {}]
  lappend K [list [llength $sequence1] [llength $sequence2] {}]
  set k 0

  # Walk through the first file, letting i be the index of the line and
  # string be the line itself.

  set i 0
  foreach string $sequence1 {

    # Consider each possible corresponding index j in the second file.

    if { [info exists eqv($string)] } {

      # c is the candidate match most recently found, and r is the
      # length of the corresponding subsequence.

      set c [lindex $K 0]
      set r 0

      foreach j $eqv($string) {

        # Perform a binary search to find a candidate common
        # subsequence to which may be appended this match.

        set max $k
        set min $r
        set s [expr { $k + 1 }]
        while { $max >= $min } {
          set mid [expr { ( $max + $min ) / 2 }]
          set bmid [lindex $K $mid 1]
          if { $j == $bmid } {
            break
          } elseif { $j < $bmid } {
            set max [expr {$mid - 1}]
          } else {
            set s $mid
            set min [expr { $mid + 1 }]
          }
        }

        # Go to the next match point if there is no suitable
        # candidate.

        if { $j == [lindex $K $mid 1] || $s > $k} {
          continue
        }

        # s is the sequence length of the longest sequence
        # to which this match point may be appended. Make
        # a new candidate match and store the old one in K
        # Set r to the length of the new candidate match.

        set newc [list $i $j [lindex $K $s]]
        lset K $r $c
        set c $newc
        set r [expr {$s + 1}]

        # If we've extended the length of the longest match,
        # we're done; move the fence.

        if { $s >= $k } {
          lappend K [lindex $K end]
          incr k
          break
        }

      }

      # Put the last candidate into the array

      lset K $r $c

    }

    incr i

  }

  set q [lindex $K $k]

  for { set i 0 } { $i < $k } {incr i } {
    lappend seta {}
    lappend setb {}
  }
  while { [lindex $q 0] >= 0 } {
    incr k -1
    lset seta $k [lindex $q 0]
    lset setb $k [lindex $q 1]
    set q [lindex $q 2]
  }

  return [list $seta $setb]

XQL Not present:

Generic, PostgreSQL, Oracle