Longest common subsequence: Difference between revisions
m
Specified the (<>) relation over matches.
Thundergnat (talk | contribs) (Undo revision 344177 by CNHume ([[Userp formatting) |
m (Specified the (<>) relation over matches.) |
||
Line 10:
Define the strict Cartesian product-order (<) over matches, such that (i1, j1) < (i2, j2) iff i1 < j1 and i2 < j2. Defining (>) similarly, we can write m2 < m1 as m1 > m2.
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
We write m1 <> m2 to mean that either m1 < m2 or m1 > m2. Thus, the (<>) operator is the inverse of (#). In this case, m1 != m2 holds, i.e., the two tuples differ in some component.
Given a product-order over the set of matches '''M''', a chain '''C''' is any subset of '''M''' where either m1 < m2 or m2 < m1 for every pair of distinct elements m1 and m2 of '''C'''.
Line 30 ⟶ 32:
In the application of comparing file revisions, records from the input files form a large symbol space; and the number of symbols may be reduced to the length of the LCS and the number of matches may tend towards linear, O(m+n) growth.
Claus Rick has also described a linear-space algorithm with a time bound of O(n*s + min(p*m, p*(n-p))).
| |||