Tìm chuỗi con chung dài nhất

1.Longest Common Subsequence Problem (LCM) :

Problem : Given two sequce x[1…m] and y[1..m] find a LCM of both .

Example :

x: A B C B DAB

y:B D C A B A

LCS(x, y) = BCBA

 

2.Brute force solution :

 

We need to check every subsequence of x[1…m] to determine that it also a subsequence of y[1…n]

Analysis :

Time to check every subsequence of x = O(n)

And we have 2m subsequence of x ( every bits with length m specific a subsequence of x[1…m])

Worst Case : O(n*2m) à Exponential Time such that we can’t apply this technique.

 

3.Dynamic programming solution ( Recursive and Tabular method )

Theorem : Let c[i,j] is the length of LCM(x[1…i] , y[1…j]). So we have :

clip_image001

This is first hall mark of Dynamic Programming call optimal substructure, that mean an optimal solution to a problem contains optimal solutions to subproblem .

In this case, If m = LCS(x, y), then any prefix of m is longest common subsequence of a prefix of x and a prefix of y.

3.1 Recursive Solution :

LCS(x, y, i, j)

if x[i] = y[ j]

then c[i, j] ← LCS(x, y, i–1, j–1) + 1

else c[i, j] ← max{LCS(x, y, i–1, j),

LCS(x, y, i, j–1)}

It also has exponential time running because overlapping subproblem.

This is second hallmark of dynamic programming (Overlapping Subproblems

There are only m*n distinct subproblem .

3.2Memoization algorithm to improve Recursive Solution :

Memoization algorithm is very simple, after computing a solution we store it in a structure than we can avoid redoing work.

LCS(x, y, i, j)

if c[i, j] = NIL

then if x[i] = y[j]

then c[i, j] ← LCS(x, y, i–1, j–1) + 1

else c[i, j] ← max{LCS(x, y, i–1, j), LCS(x, y, i, j–1)}

Complexity = O(mn) .

3.3. Tabular method :

public void LCM()

{

string x =” ” + textBox1.Text;

string y =” ” + textBox2.Text;

c = new int[x.Length+1,y.Length+1];

b = new string[x.Length+1,y.Length+1];

for(int i = 0; i< x.Length; i++)

{

c[i,0] = 0;

}

for(int j = 0; j< y.Length; j++)

{

c[0,j] = 0;

}

for(int i = 1; i< x.Length; i++)

{

for(int j = 1; j< y.Length; j++)

{

if(x[i] == y[j])

{

c[i,j] = c[i-1,j-1]+1;

b[i,j] = “ne”;

}

else if(c[i-1,j] >= c[i,j-1])

{

c[i,j] = c[i-1,j];

b[i,j] =”up”;

}

else

{

c[i,j] = c[i,j-1];

b[i,j] =”le”;

}

}

}

}

3.4 Extrack longest common subsequence :

We use recursion to extrat longest common subsequence .

public void printLCM(string x,int i,int j)

{

if (i == 0)

{

return;

}

if (j == 0)

{

return;

}

if (b[i, j] == “ne”)

{

printLCM(x, i – 1, j – 1);

result += x[i];

}

else if (b[i, j] == “up”)

{

printLCM(x, i – 1, j);

}

else

{

printLCM(x, i, j – 1);

}

}

Link tải tham khảo: http://www.mediafire.com/?z3lklae3q010o78

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s