Bilgisayar bilimlerinde önemli bir yere sahip olan bu problemde, verilen iki dizgide de ortak olarak bulunan ve aynı yönde sıralanmış dizgiler bütünü elde edilmeye çalışılmaktadır.
Örneğin;
“ABCDGH” ve “AEDFHR” için “ADH”
“AGGTAB” ve “GXTXAYB” için “GTAB”
Dosyalar arasındaki farkları, değişiklikleri elde etmede ve özellikle bioinformatik alanında sıkça karşılaşılan bir çözümdür. Çözüm aşağıdaki gibidir.
def lcs(s1, s2):
len_s1, len_s2 = len(s1) + 1, len(s2) + 1
S = [[0] * len_s1 for _ in range(len_s2)]
for i in range(1, len_s2):
for j in range(1, len_s1):
if s1[j - 1] == s2[i - 1]:
S[i][j] = S[i - 1][j - 1] + 1
else:
S[i][j] = max(S[i - 1][j], S[i][j - 1])
return S[len_s2 - 1][len_s1 - 1]
if __name__ == '__main__':
X = "AGGTAB"
Y = "GXTXAYB"
print(lcs(X, Y))
Bu algoritmanın zaman karmaşıklığı O(nm)
'dir. Peki hangi dizginin LCS olduğunu bulmak için ne yapmamız gerekiyor? Bunun için şu şekilde bir düzenleme ile sonuca ulaşabiliriz.
def lcs(s1, s2):
len_s1, len_s2 = len(s1) + 1, len(s2) + 1
S = [[0] * len_s1 for _ in range(len_s2)]
for i in range(1, len_s2):
for j in range(1, len_s1):
if s1[j - 1] == s2[i - 1]:
S[i][j] = S[i - 1][j - 1] + 1
else:
S[i][j] = max(S[i - 1][j], S[i][j - 1])
i, j = len_s2 - 1, len_s1 - 1
result = ""
while i > 0 and j > 0:
if s1[j - 1] == s2[i - 1]:
result += s1[j - 1]
i, j = i - 1, j - 1
elif S[i - 1][j] > S[i][j - 1]:
i -= 1
else:
j -= 1
return S[len_s2 - 1][len_s1 - 1], result[::-1]
if __name__ == '__main__':
X = "AGGTAB"
Y = "GXTXAYB"
print(lcs(X, Y))
Çok daha ayrıntılı bir inceleme için Wiki sayfasından yardım alabilirsiniz.
Comments
comments powered by Disqus