dp

# dynamic programming
# LCS                   22.05.17

import timeit

#sampleString1 = "abcdefgjoopf"
#sampleString2 = "abcjjahf"
sampleString1 = "thisisatest"
sampleString2 = "testing123testing"
# sampleString1 = "ABCBDAB"
# sampleString2 = "BDCABA"
# sampleString1 = "XMJYAUZ"
# sampleString2 = "MZJAWXU"

def lcsRecursive(X, Y):
    if not X or not Y:
       return ""
    x, Xs, y, Ys = X[0], X[1:], Y[0], Y[1:]
    if x == y:
       return x + lcsRecursive(Xs, Ys)
    else:
       return max(lcsRecursive(X, Ys), lcsRecursive(Xs, Y), key=len)

def lcsDP(X, Y):
    lengths = [[0 for j in range(len(Y)+1)] for i in range(len(X)+1)]

    for i, x in enumerate(X):
        for j, y in enumerate(Y):
            if x == y:
                lengths[i+1][j+1] = lengths[i][j] + 1
            else:
                lengths[i+1][j+1] = max(lengths[i+1][j], lengths[i][j+1])

    result = ""
    x, y = len(X), len(Y)
    while x != 0 and y != 0:
        if lengths[x][y] == lengths[x-1][y]:
            x -= 1
        elif lengths[x][y] == lengths[x][y-1]:
            y -= 1
        else:
            assert X[x-1] == Y[y-1]
            result = X[x-1] + result
            x -= 1
            y -= 1
    return result

dptime = timeit.default_timer()
dpLCS = lcsDP(sampleString1, sampleString2)
dptime = timeit.default_timer() - dptime

rectime = timeit.default_timer()
recLCS = lcsRecursive(sampleString1, sampleString2)
rectime = timeit.default_timer() - rectime


print("String1:\t{}\nString2:\t{}\n".format(sampleString1, sampleString2))
print("DP results:\nLCS:\t\t{}\nLCS length:\t{}\nTime:\t\t{}".format(dpLCS, len(dpLCS), dptime))
print("\nRecursive results:\nLCS:\t\t{}\nLCS length:\t{}\nTime:\t\t{}".format(recLCS, len(recLCS), rectime))