Longest common subsequence: Difference between revisions

Content added Content deleted
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: Line 10:
An ordered pair (i, j) will be called a match if ''A''[i] == ''B''[j], where 0 &le; i < m and 0 &le; j < n.
An ordered pair (i, j) will be called a match if ''A''[i] == ''B''[j], where 0 &le; i < m and 0 &le; j < n.


Define the strict Cartesian [https://en.wikipedia.org/wiki/Product_order product-order] (<) over matches, such that (i1, j1) < (i2, j2) &harr; i1 < i2 and j1 < j2. Defining (>) similarly, we can write m2 < m1 as m1 > m2.
Define the strict Cartesian [https://en.wikipedia.org/wiki/Product_order product-order] (<) over matches, such that (i1, j1) < (i2, j2) &hArr; i1 < i2 and j1 < j2. Defining (>) similarly, we can write m2 < m1 as m1 > m2.


We write m1 <> m2 to mean that either m1 < m2 or m1 > m2 holds, ''i.e.'', that m1, m2 are ''comparable''.
We write m1 <> m2 to mean that either m1 < m2 or m1 > m2 holds, ''i.e.'', that m1, m2 are ''comparable''.
Line 22: 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'''.
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 '''M''' represents a relation over match pairs: (i, j) &isin; '''M''' &hArr; '''M'''[i, j]. Any chain '''C''' can be visualized as a strictly increasing curve which passes through each match pair in the m*n coordinate space.
⚫
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] &harr; (i, j) &isin; '''M'''. Then a chain '''C''' can be visualized as a strictly increasing curve through those coordinate pairs corresponding to matches.


'''Background'''
'''Background'''
Retrieved from "https://rosettacode.org/wiki/Longest_common_subsequence"