diff.py

import sys

def diff(a, b):
    al = a.split('\n')
    bl = b.split('\n')

    ah = [hash(s) for s in al]
    bh = [hash(s) for s in bl]

    t = [[0 for j in range(0, len(bl)+1)] for i in range(0, len(al)+1)]
    p = [[(0, 0) for j in range(0, len(bl)+1)] for i in range(0, len(al)+1)]

    print "Calc diff..."
    for i in range(1, len(al)+1):
        for j in range(1, len(bl)+1):
            t[i][j] = t[i][j - 1]
            p[i][j] = (0, -1)
            if (t[i][j] < t[i - 1][j]):
                t[i][j] = t[i - 1][j]
                p[i][j] = (-1, 0)
            if (ah[i - 1] == bh[j - 1]) and (t[i][j] < t[i - 1][j - 1] + 1):
                t[i][j] = t[i - 1][j - 1] + 1
                p[i][j] = (-1, -1)

    print "Find same lines..."
    ax, bx = [], []
    i, j = len(al), len(bl)
    k = p[i][j]
    while k != (0, 0):
        if k == (-1, -1):
            ax += [i - 1]
            bx += [j - 1]
        i += k[0]
        j += k[1]
        k = p[i][j]
    ax.reverse()
    bx.reverse()

    print ax, bx
    ai, bi, ci = 0, 0, 0

    print "Show diff..."
    while ai < len(al):
        while (ai < len(al)) and (ci == len(ax) or ai < ax[ci]):
            print '-' + al[ai]
            ai += 1
        while (bi < len(bl)) and (ci == len(bx) or bi < bx[ci]):
            print '+' + bl[bi]
            bi += 1
        if (ci < len(ax)):
            print ' ' + al[ax[ci]]
            ci += 1
            ai += 1
            bi += 1

if __name__ == "__main__":
    f1 = file(sys.argv[1])
    f2 = file(sys.argv[2])
    diff(f1.read(), f2.read())