Lab7

def find_ED(s1, s2):
    m = len(s1)
    n = len(s2)
    matrix = [[0 for _ in range(0, n+1)] for _ in range(0, m+1)]

    # initialize first column and first row
    for i in range(0, m+1):
        matrix[i][0] = i
    for j in range(1, n+1):
        matrix[0][j] = j

    # finds shortest distance from top left to bottom right
    for k in range(1, m+1):
        for l in range(1, n+1):
            diff = 0 if(s1[k-1] == s2[l-1]) else 1
            matrix[k][l] = min(matrix[k-1][l] + 1, matrix[k][l-1] + 1, matrix[k-1][l-1] + diff)

    # backtrace to build right alignment, go from bottom right to top left
    as1 = ""
    as2 = ""
    d = matrix[m][n]
    while (m > 0) or (n > 0):
        # move diagonally on backtrace, build string accordingly
        if (m > 0) and (n > 0) and (matrix[m-1][n-1] <= matrix[m][n-1]) and (matrix[m-1][n-1] <= matrix[m-1][n]):
            m = -1 if(m == -1) else m-1
            n = -1 if(n == -1) else n-1
            as1 = s1[m] + as1
            as2 = s2[n] + as2
        # move up on backtrace, build string accordingly
        elif(matrix[m][0 if(n <= 0) else n-1] <= matrix[0 if(m<=0) else m-1][n]):
            n = -1 if(n == -1) else n-1
            as1 = "_" + as1
            as2 = s2[0 if (n == -1) else n] + as2
        # move left on backtrace, build string accordingly
        else:
            m = -1 if(m == -1) else m-1
            as1 = s1[0 if (m == -1) else m] + as1
            as2 = "_" + as2
    print(as1)
    print(as2)
    return d

word1 = raw_input('Enter in String 1:')
word2 = raw_input('Enter in String 2:')

edit_d = find_ED(word1,word2)
print 'The edit distance is {}'.format(edit_d)