Maximum public subsequence

•

/ * If the given sequence x = {x1, x2, ..., xm}, the other sequence z = {z1, z2, ..., zk}, is the subsequence of X means there is a strict incremental subscript sequence {I1 , I2, ..., IK} makes all J = 1, 2, ..., k are: zj = xij. For example, sequence z = {B, C, D, B} is a subsequence of sequence x = {A, B, C, B, D, A, B}, and corresponding incremental subsequent sequence is {2, 3, 5 . • Two sequences x and y are given, when another sequence z is both a subsequence of X is still a subsequence of Y, called Z is a common subsequence of sequence x and y.

• 2 Sequences x = {x1, x2, ..., xm}, and y = {Y1, Y2, ..., YN}, find the longest common subsequence of X and Y.

* /

/ ************************************************** ********************* REVISION log entry revision by: http://blog.9cbs.net/hongweijin revised on 2005-3-23 16:39:35 Comments: Dynamic planning method for maximum increasing sequence, *********************************************************** *** /

#include #include

INT Creatlist (int Source []); Void getlongeestList (int Source [], int LENGTH);

Void main () {Int Source [100]; int LENGTH;

Length = CreatList (Source); getlongeestList (Source, Length);}

///// / / Function Name: getlongestList // Function Description: Get the longest predecessor sequence // Parameters: int order [] // Parameters: int lay // Return Value: void //// Void getlongestList ( Int Source [], intlene) {INT I, J, NEXTJ, * MAX, * TEMP, Client = 0, LENTEMP; / / / / MAX evaluation algorithm: // through "Dynamic Planning Law": Select on the left One, assume that this point is in // The elder sequence, then I know that the problem is divided into two parts, the previous and // current number. If you can give the optimal structure in front, then add the current // point, you can find this idea, we can start from the left, for the first // number, his longest number should be 1, then examine the following elements, in the foregoing / / optimal, the back of the back is optimal. // Recurrent relationship: // max [i] = max (max [j] 1) // 1 <= j <= I // source [j] <= source [i] // // as follows : 1 3 7 4 8 2 9 0 4 // The result of the max value is: 1 2 3 3 4 2 5 1 3 //, such as 8 this element, there are one 3 4 8 such a series / // Max = (int *) malloc (INT) * Length); // If max is not compared to 1 length for (i = 0; i Source [J]) {IF (Client

/// printf ("/ n printing Each element is assumed in the number of: / n"); for (i = 0; i client) {client = max [ i]; j = i;} // Used to adjust the direction of the result of LENTEMP = Client; Temp = (int *) Malloc (INT) * LENTEMP; TEMP [Client] = Source [J]; // Print Small cycle while (client> 1) {--client; for (i = 0; i = max [i]) { Temp [client] = source [i]; nextj = i;}} j = nextj;}} j = nextj;} for (i = 1; i <= lentemp; i ) {printf ("% d", temp [i]);} printf ("/ n");} ////// Function Name: CreatList // Function Description: Input Sequence // Parameters: Int Source [100] // Return Value: void //// Int Creatlist (int " Source [100]) {INT I, J;

Printf ("Please enter the sequence, and input: / n" in -1); for (i = 0; i <100; i ) {scanf ("% d", & j); if (j == -1) Break; Else Source [i] = j;} Return i;}