Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Longest Common Subsequence Dynamic programming
- # R@1313I
- def lcs(X, Y):
- # find the length of the strings
- m = len(X)
- n = len(Y)
- # Array for storing Dynamic Value
- L = [[None] * (n + 1) for i in range(m + 1)]
- # Implying the LCS Algorithm
- 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])
- # Sending the result L[m][n]
- return L[m][n]
- Get1stInput = input("Input Some Character For Sequences: ")
- X = Get1stInput.upper()
- Get2ndInput = input("Input Some More Character For Checking LCS: ")
- Y = Get2ndInput.upper()
- print("Length of LCS in the given Character is ", lcs(X, Y))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement