lcs.py

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)