Longest common subsequence: Difference between revisions

Content added Content deleted
m (Simplified Rick's time bound. Made additional editorial improvements.)
m (Clarified contrast between comparable vs. incomparable tuples.)
Line 14: 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''.
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. ''Note:'' This includes the possibility that m1 == m2, ''i.e.'', that i1 == i2 and j1 == j2.
Defining (#) to denote this case, we write m1 # m2. Because the underlying product order is strict, m1 == m2 (''i.e.'', i1 == i2 and j1 == j2) implies m1 # m2.


We write m1 <> m2 to mean that ''either'' m1 < m2 ''or'' m1 > m2 holds. Thus, the (<>) operator is the inverse of (#). In this case, m1 != m2, ''i.e.'', each of tuples differ in some component.
We write m1 <> m2 to mean that ''either'' m1 < m2 ''or'' m1 > m2 holds, ''i.e.'', that m1, m2 are ''comparable''. Thus the (<>) operator is the inverse of (#).

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'''.
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: Line 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'''.
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 there is a match at the corresponding positions of strings ''A'' and ''B''.
The set of matches '''M''' can be visualized as an m*n bit matrix, where each bit '''M[i, j]''' is True iff the ordered pair (i, j) is in the set.


Then any chain '''C''' can be visualized as a strictly increasing curve through those match bits which are set to True.
Then any chain '''C''' can be visualized as a strictly increasing curve through those match bits which are True.


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