Longest common subsequence: Difference between revisions

Longest common subsequence (view source)

10 bytes added , 2 years ago

Restored original string names of A and B, since coding samples were based on that assumption.

159

edits

Revision as of 07:12, 21 September 2021 (view source) CNHume (talk \| contribs) m (Found one more font face change to make.) ← Older edit		Revision as of 07:52, 21 September 2021 (view source) CNHume (talk \| contribs) (Restored original string names of A and B, since coding samples were based on that assumption.) Newer edit →
Line 4: The '''Longest Common Subsequence''' (or [http://en.wikipedia.org/wiki/Longest_common_subsequence_problem '''LCS''']) is a subsequence of maximum length common to two (or more) strings. Let xA = xA[0]~~...~~… xA[m-1] and yB = yB[0]~~...~~… yB[n-1], m <= n be strings drawn from an alphabet '''Σ''' of size s, containing every distinct symbol in xA + yB. An ordered pair (i, j) will be called a match if xA[i] == yB[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. Line 14: 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 also be ~~represented~~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 xA and yB. ~~Any~~Then any chain '''C''' can ~~then~~ be visualized as a monotonically increasing curve through those match bits which are set to True. For example, the sequences "1234" and "1224533324" have an LCS of "1234":