FilesExpand file tree

 master

/

lcs.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

28 lines (22 loc) · 740 Bytes

 master

/

lcs.py

Copy path

Top

File metadata and controls

• Code
• Blame

28 lines (22 loc) · 740 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

# Dynamic Programming implementation of LCS problem

def lcs(X , Y):

# find the length of the strings

m = len(X)

n = len(Y)

# declaring the array for storing the dp values

L = [[None]*(n+1) for i in xrange(m+1)]

for i in range(m+1):

for j in range(n+1):

if i == 0 or j == 0 :

L[i][j] = 0

elif X[i-1] == Y[j-1]:

L[i][j] = L[i-1][j-1]+1

else:

L[i][j] = max(L[i-1][j] , L[i][j-1])

# L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]

return L[m][n]

#end of function lcs

# Driver program to test the above function

X = "AGGTAB"

Y = "GXTXAYB"

print "Length of LCS is ", lcs(X, Y)