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.

$LCS\left(X_{i},Y_{j}\right) = \begin{cases} \empty & \mbox{ if }\ i = 0 \mbox{ or } j = 0 \\ \textrm{ ( } LCS\left(X_{i-1},Y_{j-1}\right), x_i) & \mbox{ if } x_i = y_j \\ \mbox{longest}\left(LCS\left(X_{i},Y_{j-1}\right),LCS\left(X_{i-1},Y_{j}\right)\right) & \mbox{ if } x_i \ne y_j \\ \end{cases}$

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