Longest common subsequence: Difference between revisions
Content added Content deleted
(Clarified statement of the Longest Common Subsequence Problem) |
m (Replaced use of the word Sigma with the actual Greek Letter. Used bold font for emphasis.) |
||
Line 4: | 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. |
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 x = x[0]... x[m-1] and y = y[0]... y[n-1], m <= n be strings drawn from an alphabet |
Let x = x[0]... x[m-1] and y = y[0]... y[n-1], m <= n be strings drawn from an alphabet '''Σ''' of size s, containing every distinct symbol in x + y. |
||
An ordered pair (i, j) will be called a match if x[i] == y[j], where 0 <= i < m and 0 <= j < n. |
An ordered pair (i, j) will be called a match if x[i] == y[j], where 0 <= i < m and 0 <= j < n. |
||
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 the LCS can then be viewed as the problem of finding a chain of maximum cardinality over the set of matches M. |
Finding the 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. |
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. |
||
A chain can then be visualized as any monotonically increasing curve through those match bits which are set to True. |
A chain can then be visualized as any monotonically increasing curve through those match bits which are set to True. |