1def lcs(X, Y):
2
3 n = len(Y)
4 m = len(X)
5
6 L = [[None]*(n + 1) for i in range(m + 1)]
7 for i in range(m + 1):
8 for j in range(n + 1):
9 if i == 0 or j == 0 :
10 L[i][j] = 0
11 elif X[i-1] == Y[j-1]:
12 L[i][j] = L[i-1][j-1]+1
13 else:
14 L[i][j] = max(L[i-1][j], L[i][j-1])
15
16 return L[m][n]