Longest common subsequence: Difference between revisions
m
Added definition of "incomparable" matches.
(Restored original string names of A and B, since coding samples were based on that assumption.) |
m (Added definition of "incomparable" matches.) |
||
Line 8:
An ordered pair (i, j) will be called a match if A[i] == B[j], where 0 <= i < m and 0 <= j < n.
Define
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 such a product-order over a set of matches '''M''', a chain '''C''' is any subset of '''M''' where either p1 < p2 or p2 < p1, for distinct pairs p1 and p2 in '''C'''.▼
▲Given
Finding an '''LCS''' can then be stated as the problem of finding a chain of maximum cardinality over the set of matches '''M'''.▼
▲Finding an '''LCS''' can then be
This set of matches can also 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.▼
▲
Then any chain '''C''' can be visualized as a monotonically increasing curve through those match bits which are set to True.
| |||