Longest common subsequence: Difference between revisions
m
Clarified contrast between comparable vs. incomparable tuples.
m (Simplified Rick's time bound. Made additional editorial improvements.) |
m (Clarified contrast between comparable vs. incomparable tuples.) |
||
Line 14:
If i1 <= j1 and i2 >= j2 (or i1 >= i2 and i2 <= j2) then ''neither'' m1 < m2 ''nor'' m1 > m2 are possible; and m1, m2 are ''incomparable''.
Defining (#) to denote this case, we write m1 # m2.
We write m1 <> m2 to mean that ''either'' m1 < m2 ''or'' m1 > m2 holds, ''i.e.'', that
Because the product order is strict, m1 <> m2 implies m1 != m2, ''i.e.'', that the tuples differ in some component.
Given a product-order over the set of matches '''M''', a chain '''C''' is any subset of '''M''' where m1 <> m2 for every pair of distinct elements m1 and m2 of '''C'''.
Line 22 ⟶ 24:
Finding an '''LCS''' can then be restated as the problem of finding a chain of maximum cardinality p over the set of matches '''M'''.
The set of matches '''M''' can be visualized as an m*n bit matrix, where each bit '''M[i, j]''' is True iff
Then any chain '''C''' can be visualized as a strictly increasing curve through those match bits which are
'''Background'''
| |||