Jump to content

Longest common subsequence: Difference between revisions

Longest common subsequence (view source)

Revision as of 07:05, 21 September 2021

19 bytes added ,  2 years ago
m
Minor editorial improvements.
m (Replaced use of the word Sigma with the actual Greek Letter. Used bold font for emphasis.)
m (Minor editorial improvements.)
Line 8:
An ordered pair (i, j) will be called a match if x[i] == y[j], where 0 <= i < m and 0 <= j < n.
 
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.
 
Finding thean '''LCS''' can then be viewed 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.
 
AAny chain '''C''' can then be visualized as anya monotonically increasing curve through those match bits which are set to True.
 
For example, the sequences "1234" and "1224533324" have an LCS of "1234":
CNHume
159

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/72682"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information