def initialize_array(l1, l2):
    a = []
    for i in xrange(l1):
        a.append([None]*l2)
    return a

def matchscore(c1,c2):
    if(c1 == c2):
        return 1
    return -1

def traceback(scores,locations, position, path):
    (i,j) = position
    path.insert(0,position)
    if(locations[i][j] is not None):
        nextpos = locations[i][j]
        traceback(scores,locations,nextpos,path)
    return path

def driver(s1,s2,e=-1):
    l1 = len(s1)+1
    l2 = len(s2)+1
    scores = initialize_array(l1,l2)
    locations = initialize_array(l1,l2)

    # init first row/col

    for i in xrange(l1):
        # first column
        scores[i][0] = i*e
        locations[i][0] = (i-1,0)
    for i in xrange(l2):
        # first row
        scores[0][i] = i*e
        locations[0][i] = (0,i-1)
        
    locations[0][0] = None

    # fill matrix

    for i in xrange(1,l1):
        for j in xrange(1,l2):
            # How is a match worth?
            match = scores[i-1][j-1]+matchscore(s1[i-1],s2[j-1])
            vgap = scores[i-1][j] +e
            hgap = scores[i][j-1] +e
            # Pick best
            n = max(match, vgap, hgap)
            scores[i][j] = n
            if(n == match):
                locations[i][j] = (i-1,j-1)
            elif(n == vgap):
                locations[i][j] = (i-1,j)
            else:
                locations[i][j] = (i,j-1)

    best_score = scores[-1][-1]

    path = traceback(scores,locations, (l1-1, l2-1), [])

    a1 = ""
    a2 = ""
    oldi = 0
    oldj = 0
    for (i,node) in enumerate(path[1:]):
        newi = node[0]
        newj = node[1]
        if((newi == oldi+1) and (newj == oldj +1)):
            a1 += s1[newi-1]
            a2 += s2[newj-1]
        elif((newi == oldi+1) and (newj == oldj)):
            a1 +=  s1[newi-1]
            a2 += "-"
        else:
            a1 += "-"
            a2 += s2[newj-1]
        (oldi, oldj) = (newi, newj)

    print a1
    print a2

    return (a1, a2, best_score)