Longest common subsequence problem.

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

 

LCS function defined

Let two sequences be defined as follows: X = (x₁, x₂...x_m) and Y = (y₁, y₂...y_n). The prefixes of X are X_{1, 2,...m}; the prefixes of Y are Y_{1, 2,...n}. Let LCS(X_i, Y_j) represent the set of longest common subsequence of prefixes X_i and Y_j. This set of sequences is given by the following.

To find the longest subsequences common to X_i and Y_j, compare the elements x_i and y_i. If they are equal, then the sequence LCS(X_i-1, Y_j-1) is extended by that element, x_i. If they are not equal, then the longer of the two sequences, LCS(X_i, Y_j-1), and LCS(X_i-1, Y_j), is retained. (If they are both the same length, but not identical, then both are retained.) Notice that the subscripts are reduced by 1 in these formulas. That can result in a subscript of 0. Since the sequence elements are defined to start at 1, it was necessary to add the requirement that the LCS is empty when a subscript is zero.

 

http://www.csie.ntnu.edu.tw/~u91029/LongestCommonSubsequence.html 

• 上一篇 Create different sdi windows.
• 下一篇 活用regex的例子 zz.