[go: up one dir, main page]
Scribd
Upload
8 views13 pages

LCS 1

The document discusses the Longest Common Subsequence (LCS) problem, detailing various methods for its computation including recursion, memorization, and dynamic programming. It provides examples of string pairs and their respective subsequences, along with algorithmic implementations and complexity analysis. The document emphasizes the importance of LCS in comparing strings and its applications in fields such as bioinformatics and data comparison.

Uploaded by

rsinglame24
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views13 pages

LCS 1

The document discusses the Longest Common Subsequence (LCS) problem, detailing various methods for its computation including recursion, memorization, and dynamic programming. It provides examples of string pairs and their respective subsequences, along with algorithmic implementations and complexity analysis. The document emphasizes the importance of LCS in comparing strings and its applications in fields such as bioinformatics and data comparison.

Uploaded by

rsinglame24
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 13

Longest Common Subsequence

• What is LCS
• LCS using Recursion
• LCS using Memorization
• LCS using Dynamic Programming
Longest Common Subsequence
• String 1 : abcdefghij
• String 2 : cdgi

• Subsequence matching c d g i
• dgi
• gi
Longest Common Subsequence
• String 1 : abcdefghij
• String 2 : ecdgi

• Subsequence matching c g i
• cdgi
Longest Common Subsequence
• String 1 : abdace
• String 2 : babce

• Subsequence matching b a c e
• abce
Longest Common Subsequence
• A - b d \#
• B - a b c d \#

int LCS(i,j)
{
if(A[i]==‘\#’ || B[j]==‘\#’)
return 0;
elseif (A[i]==B[i])
return 1+ LCS(i+1,j+1);
else
return max(LCS(i+1,j), LCS(i,j+1));

}
Longest Common Subsequence
• A - b d \#
A[0] B[0] 2
• B - a b c d \# b a

A[1] B[0] 1 A[0] B[1] 2


d a b b

A[2] B[0] A[1] B[1] 1+A[1] B[2]


0 1 d c
# a d b

A[2] B[1] A[1] B[2]


0 1
# b d c

A[2] B[2] A[1] B[3] 1


0
# c d d

1+A[2] B[4]
# #
Longest Common Subsequence
a b c d \#
0 1 2 3 4
b 0 2 2
d 1 1 1 1 1
\# 2 0 0 0 0

O(mxn)
Longest Common Subsequence
A - b d

B - a b c d

a b c d
0 1 2 3 4
0 0 0 0 0 0
b 1 0 0 1 1 1
d 2 0 0 1 1 2
Longest Common Subsequence
A - b d

B - a b c d

a b c d If(A[i]==B[j])
LCS[i,j] = 1 + LCS[i-1,j-1]
0 1 2 3 4 else
0 0 0 0 0 0 LCS[i,j] = max(LCS[i-1,j], LCS[i,j-1])
b 1 0 0 1 1 1
d 2 0 0 1 1 2
Longest Common Subsequence
A - b d
1 2
B -
a b c d
1 2 3 4

a b c d If(A[i]==B[j])
0 1 2 3 4 LCS[i,j] = 1 + LCS[i-1,j-1]
else
0 0 0 0 0 0
LCS[i,j] = max(LCS[i-1,j], LCS[i,j-1])
b 1 0 0 1 1 1
d 2 0 0 1 1 2
Longest Common Subsequence
A - b d

B - a b c d

a b c d If(A[i]==B[j])
LCS[i,j] = 1 + LCS[i-1,j-1]
0 1 2 3 4 else
0 0 0 0 0 0 LCS[i,j] = max(LCS[i-1,j], LCS[i,j-1])
b 1 0 0 1 1 1
d 2 0 0 1 1 2 subsequence bd

O(mxn)
Longest Common Subsequence
Str1: stone

Str2: longest

l o n g e s t
0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
S 1 0 0 0 0 0 0 1 1
T 2 0 0 0 0 0 0 1 2
O 3 0 0 1 1 1 1 1 2
N 4 0 0 1 2 2 2 2 2
E 5 0 0 1 2 2 3 3 3
Longest Common Subsequence
Str1: stone

Str2: longest

l o n g e s t
0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
S 1 0 0 0 0 0 0 1 1
T 2 0 0 0 0 0 0 1 2
O 3 0 0 1 1 1 1 1 2
N 4 0 0 1 2 2 2 2 2 O(mxn)
E 5 0 0 1 2 2 3 3 3
one

You might also like