An example analysis of the longest common subsequence problem (LCS) of Java algorithm

This paper describes the longest common subsequence problem (LCS) of Java algorithm. Share with you for your reference, as follows:

Problem Description: the subsequence of a given sequence is the sequence obtained by deleting several elements in the sequence. Specifically, if a given sequence x = {x1, X2,..., XM}, another sequence z = {Z1, Z2, ZK} is a subsequence of X, which means that there is a strictly increasing subscript sequence {I1, I2, IK}, so that for all j = 1,2, K there is Xij = ZJ. For example, sequence z = {B, C, D, B} is a subsequence of sequence x = {a, B, a, B}, and the corresponding incremental subscript sequence is {2,3,5,7}. Given two sequences X and y, when the other sequence Z is both a subsequence of X and a subsequence of Y, Z is said to be a common subsequence of sequences X and y. For example, if x = {a, B} and y = {B, a}, the sequence {B, a} is a common subsequence of X and y, and the sequence {B, a} is also a common subsequence of X and y. Moreover, the latter is the longest common subsequence of X and y, because X and y have no common subsequence with a length greater than 4. Given two sequences x = {x1, XM} and y = {Y1, Y2, yn}, it is required to find the longest common subsequence of X and y.

Problem analysis: let x = {a, B}, y = {B, a}. The easiest way to find the longest common subsequence of X and Y is exhaustive method. For multiple subsequences of X, check whether it is also a subsequence of Y, so as to determine whether it is a common subsequence of X and y. According to the properties of the set, the set with element M has 2 ^ m different subsequences. Therefore, the exhaustive method needs exponential operation time. By further decomposing the characteristics of the problem, the longest common subsequence problem actually has the property of optimal substructure.

Let the longest common subsequence of sequences x = {x1,... XM} and y = {Y1,... Yn} be z = {Z1,... ZK}. Then there are:

(1) If XM = YN, then ZK = XM = YN, and ZK-1 is the longest common subsequence of XM-1 and yn-1. (2) If XM= Yn and ZK= XM, then Z is the longest common subsequence of XM-1 and y. (3) If XM= Yn and ZK= YN, then Z is the longest common subsequence of X and yn-1. Where, XM-1 = {x1, X2... XM-1}, yn-1 = {Y1, Y2... Yn-1}, ZK-1 = {Z1, Z2... ZK-1}.

Recurrence relation: use C [i] [J] to record the length of the longest common subsequence of sequences Xi and YJ. Where xi = {x1, X2... Xi}, YJ = {Y1, Y2... YJ}. When I = 0 or j = 0, the empty sequence is the longest common subsequence of Xi and YJ. At this time, C [i] [J] = 0; When I, J > 0, xi = YJ, C [i] [J] = C [I-1] [J-1] + 1; When I, J > 0, Xi= When YJ, C [i] [J] = max{C [i] [J-1], C [I-1] [J]}, so the recurrence relationship is established as follows:

Constructing the optimal solution: from the above analysis, to find the longest common subsequence of x = {x1,... Yn}, we can recursively proceed in the following way: when XM = YN, find the longest common subsequence of XM-1 and yn-1, and then add XM (= yn) to the tail to get the longest common subsequence of X and y. When XM= In YN, two subproblems must be solved, that is, find a longest common subsequence of XM-1 and Y and a longest common subsequence of X and yn-1. The longest of the two common subsequences is the longest common subsequence of X and y. Let the value of array B [i] [J] record C [i] [J] be obtained from the solution of which sub problem, start from B [M] [n], and search in array B according to its value. When B [i] [J] = 1, it means that the longest common subsequence of Xi and YJ is the subsequence obtained by adding Xi to the tail of the longest common subsequence of XI-1 and yj-1. When B [i] [J] = 2, the longest common subsequence of Xi and YJ is the same as that of XI-1 and yj-1. When B [i] [J] = 3, the longest common subsequence of Xi and YJ is the same as that of Xi and yj-1.

The code is as follows:

Operation results:

For more information about Java algorithms, readers who are interested can see the topics on this site: Java data structure and algorithm tutorial, summary of Java DOM node operation skills, summary of java file and directory operation skills, and summary of Java cache operation skills