Longest common subsequence: Difference between revisions
m
Minor editorial correction.
m (Added definition of "incomparable" matches.) |
m (Minor editorial correction.) |
||
Line 12:
If i1 <= j1 and i2 >= j2 (or if i1 >= i2 and i2 <= j2) then neither m1 < m2 nor m1 > m2 are possible; and m1, m2 are said to be "incomparable". Defining (<>) to denote this case, we write m1 <> m2.
Given a product-order over the set of matches '''M''', a chain '''C''' is any subset of '''M''' where either m1 < m2 or m2 < m1 for
Finding an '''LCS''' can then be restated as the problem of finding a chain of maximum cardinality over the set of matches '''M'''.
| |||