Untitled 3

Substrings.py

# iPad
import console
console.clear()

# Program

def maxSub(a, b):
  table = {}
  # Base cases, Empty strings
  for i in range(0, len(a) + 1):
    table[i] = {0: ''}
  
  # go through non base cases
  for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
      # if same letter (minus one because 0 is 0 length not 0 index)
      if a[i - 1] == b[j - 1]:
        # set the value to the diagonal left-up and append that letter
        table[i][j] = table[i - 1][j - 1] + a[i - 1]
      else:
        value = ''
        if j in table[i - 1]:             # if j is defined in i-1
          value = table[i - 1][j]         # that is the value
        if j - 1 in table[i]:
          possible = table[i][j - 1]
          if len(possible) > len(value):  # if j -1 is longer than our current subsequence
            value = possible              # assign it
        table[i][j] = value               # now value is guranteed to be the longest sub
  return table[len(a)][len(b)]            # return the farthest cell
  
def maxSubString(a, b):
  table = {}
  for i in range(0, len(a) + 1):
    table[i] = {0: ''}
  
  best_i = -1
  best_j = -1
  
  for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
      if a[i - 1] == b[j - 1]:
        table[i][j]= table[i - 1][j - 1] + a[i - 1]
        # Keep track of the longest sucession
        if best_i == -1 or len(table[best_i][best_j]) < len(table[i][j]):
          best_i, best_j = i, j
      else:
        table[i][j] = ''
  
  if best_i == -1:
    return ''
  else:
    return table[best_i][best_j]
  

values = {"batx": "atv", "Mohammad": "Eric", "Ruth": "Truth", "first": "ist"}
for key, value in values.iteritems():
  print("{} U {} = {}".format(key, value, maxSub(key, value)))
  
for key, value in values.iteritems():
  print("maxSubString(\"{}\", \"{}\") = {}".format(key, value, maxSubString(key, value)))

Mohammad U Eric = 
Ruth U Truth = uth
first U ist = ist
batx U atv = at
maxSubString("Mohammad", "Eric") = 
maxSubString("Ruth", "Truth") = uth
maxSubString("first", "ist") = st
maxSubString("batx", "atv") = at