Longest common subsequence: Difference between revisions
m
Revised interpretation of M as a relation.
m (Improved discussion of M interpreted as an m*n boolean matrix. Simplified O(n) terms.) |
m (Revised interpretation of M as a relation.) |
||
Line 10:
An ordered pair (i, j) will be called a match if ''A''[i] == ''B''[j], where 0 ≤ i < m and 0 ≤ j < n.
Define the strict Cartesian [https://en.wikipedia.org/wiki/Product_order product-order] (<) over matches, such that (i1, j1) < (i2, j2) &
We write m1 <> m2 to mean that either m1 < m2 or m1 > m2 holds, ''i.e.'', that m1, m2 are ''comparable''.
Line 22:
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
According to [Dilworth 1950], this cardinality p equals the minimum number of disjoint antichains into which '''M''' can be decomposed. Note that such a decomposition into the minimal number p of disjoint antichains may not be unique.▼
▲According to [Dilworth 1950], this cardinality p equals the minimum number of disjoint antichains into which '''M''' can be decomposed. Note that such a decomposition into the minimal number p of disjoint antichains may not be unique.
▲The set of matches '''M''' can be interpreted as an m*n boolean matrix such that '''M'''[i, j] ↔ (i, j) ∈ '''M'''. Then a chain '''C''' can be visualized as a strictly increasing curve through those coordinate pairs corresponding to matches.
'''Background'''
| |||