Created
January 7, 2019 22:16
-
-
Save jlegutko/5b84cb02739eac88adf9b8a5b522d776 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def LongestCommonSubstring(string1, string2): | |
max_length = max(len(string1),len(string2)) | |
min_length = min(len(string1),len(string2)) | |
# sprawdzenie które słowo jest krótsze | |
if len(string1)>=len(string2): | |
long_str = string1 | |
short_str = string2 | |
else: | |
long_str = string2 | |
short_str = string1 | |
#uzupełnienie wierszami słownika, dodanie wartosci poczatkowych do tablic | |
row1=[] | |
for i in range(0, max_length+1): | |
row1.append(0) | |
str_dict = {} | |
str_dict[0] = row1 | |
for i in range(1, min_length+1): | |
str_dict[i]=[0] | |
#wyliczenie wszystkich elementów wierszy | |
for j in range(0,min_length): | |
for k in range(0,max_length): | |
if long_str[k] == short_str[j]: | |
change = (str_dict[j][k]) + 1 | |
str_dict[j+1].append(change) | |
else: | |
no_change = max(str_dict[j+1][k], str_dict[j][k+1]) | |
str_dict[j+1].append(no_change) | |
#Najdluzszy podciag | |
j = min_length | |
k = max_length | |
lcs_string = str() | |
removed_str = str() | |
while j!=0 and k!=0: | |
if str_dict[j][k] == str_dict[j-1][k] and str_dict[j][k] == str_dict[j][k-1]: | |
j-=1 | |
elif (str_dict[j][k] != str_dict[j-1][k] and str_dict[j][k] == str_dict[j][k-1])or (str_dict[j][k] == str_dict[j-1][k] and str_dict[j][k] != str_dict[j][k-1]): | |
k-=1 | |
elif str_dict[j][k] != str_dict[j-1][k] and str_dict[j][k] != str_dict[j][k-1]: | |
lcs_string = lcs_string + long_str[k-1] | |
if j!=0 and k!=0: | |
j-=1 | |
k-=1 | |
else: | |
pass | |
lcs = 1-(str_dict[min_length][max_length]/max_length) | |
print('LCS(string_1, string_2) = ' + str(lcs)) | |
print('Najdluzszy wspolny podciag to: ' + lcs_string[::-1]) | |
print('f(string_1, string_2) = ' + str(str_dict[min_length][max_length])) | |
print(str_dict) | |
return lcs | |
string_1 = input('Podaj pierwszy ciąg:') | |
string_2 = input('Podaj drugi ciąg:') | |
LongestCommonSubstring(string_1, string_2) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment