Zaprojektuj algorytm do znajdowania najdłuższego wspólnego podciągu między dwoma ciągami znaków.
s1 = 'ABCDGH'
s2 = 'AEDFHR'
def LCS(s1, s2): 
m = len(s1) 
n = len(s2)

# declaring the array for storing the dp valoes 
L = [[None]*(n + 1) for _ in range(m + 1)] 

"""Following steps build L[m + 1][n + 1] in bottom op fashion 
Note: L[i][j] contains length of LCS of X[0..i-1] 
and Y[0..j-1]"""
for i in range(m + 1): 
# previoios row is all zeros, 
# as no common sequence can make using them 
for j in range(n + 1): 
# first columns of all rows are 0 
if i == 0 or j == 0 : 
L[i][j] = 0
elif s1[i-1] == s2[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] 
retorn L[m][n]