from numpy import *

def LCS(v, w):
    s = zeros((len(v)+1,len(w)+1), dtype=int32)
    b = zeros((len(v)+1,len(w)+1), dtype=int32)
    for i in xrange(1,len(v)+1):
        for j in xrange(1,len(w)+1):
            if (v[i-1] == w[j-1]):
                s[i,j] = max(s[i-1,j], s[i,j-1], s[i-1,j-1] + 1)
            else:
                s[i,j] = max(s[i-1,j], s[i,j-1])
            if (s[i,j] == s[i,j-1]):
               b[i,j] = 1
            elif (s[i,j] == s[i-1,j]):
               b[i,j] = 2
            else:
               b[i,j] = 3
    return (s[i,j], b)


def PrintLCS(b,v,w,i,j,result=[]):
    if ((i == 0) or (j == 0)):
        print
        print " ".join([t[0] for t in result])
        print " ".join([t[1] for t in result])
        print " ".join([t[2] for t in result])
        print
        print "LCS =",
        return
    if (b[i,j] == 3):
        result = [(v[i-1], "|", w[j-1])] + result
        PrintLCS(b,v,w,i-1,j-1,result)
        print v[i-1],
    else:
        if (b[i,j] == 2):
            result = [(v[i-1], " ", "_")] + result
            PrintLCS(b,v,w,i-1,j,result)
        else:
            result = [("_", " ", w[j-1])] + result
            PrintLCS(b,v,w,i,j-1,result)


if __name__ == "__main__":
    import sys
    print "Largest Common Subsequence algorithm in Python (page 176)"
    if (len(sys.argv) == 3):
        v = sys.argv[1]
        w = sys.argv[2]
    else:
        v = raw_input('v string: ')
        w = raw_input('w string: ')

    s, b = LCS(v, w)
    print "score =", s
    PrintLCS(b,v,w,len(v),len(w))
    print
    raw_input('Press [Enter] to quit.')