Longest common subsequence: Difference between revisions
Content added Content deleted
m (Minor editorial improvements.) |
m (Found one more font face change to make.) |
||
| Line 10: | Line 10: | ||
Define a strict Cartesian product-order (<) over these ordered pairs, such that (i1, j1) < (i2, j2) iff i1 < j1 and i2 < j2. |
Define a strict Cartesian product-order (<) over these ordered pairs, such that (i1, j1) < (i2, j2) iff i1 < j1 and i2 < j2. |
||
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 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'''. |
||
Finding an '''LCS''' can then be |
Finding an '''LCS''' can then be stated as the problem of finding a chain of maximum cardinality over the set of matches '''M'''. |
||
This set of matches can be represented 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 x and y. |
This set of matches can be represented 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 x and y. |
||