Longest common subsequence: Difference between revisions
Simplified discussion of the product-order, defining it to be non-strict in keeping with wider convention. Corrected legend.
m (Revised interpretation of M as a relation.) |
(Simplified discussion of the product-order, defining it to be non-strict in keeping with wider convention. Corrected legend.) |
||
Line 6:
The [http://en.wikipedia.org/wiki/Longest_common_subsequence_problem '''Longest Common Subsequence'''] ('''LCS''') is a subsequence of maximum length common to two or more strings.
Let ''A''
An ordered pair (i, j) will be
Define the
We
Given a product-order over the set of matches '''M''', a chain '''C''' is any subset of '''M'''
The set '''M''' represents a relation over match pairs:
Finding an LCS can
▲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'''. Similarly, an antichain '''D''' is any subset of '''M''' where m1 # m2 for every pair of distinct elements m1 and m2 of '''D'''.
▲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) ∈ '''M''' ⇔ '''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.
Line 46 ⟶ 42:
A, B are input strings of lengths m, n respectively
p is the length of the LCS
M is the set of match pairs (i, j) such that
r is the magnitude of M
s is the magnitude of the alphabet Σ of distinct symbols in
'''References'''
| |||