import sys,time
def mem(f):
    memory = {}
    def inner_function(*args):
        if args not in memory:            
            memory[args] = f(*args)
        return memory[args]
    return inner_function

def myLCS(X, Y, m, n):
    if (m == 0 or n == 0):
        return 0
    if (X[m - 1] == Y[n - 1]):
        return 1 + myLCS(X, Y, m - 1, n - 1)
    else:
        return max(myLCS(X, Y, m, n - 1),
                   myLCS(X, Y, m - 1, n))

@mem
def lcs(X, Y, m, n):
    if (m == 0 or n == 0):
        return 0
    if (X[m - 1] == Y[n - 1]):
        return 1 + lcs(X, Y, m - 1, n - 1)
    else:
        return max(lcs(X, Y, m, n - 1),
                   lcs(X, Y, m - 1, n))
w1 = (input("word 1? "))
w2 = (input("word 2? "))
start_time = time.time()
print(lcs(w1,w2,len(w1),len(w2)))
print ("Time taken for memoized function was ", \
                (time.time() - start_time)," seconds.")
start_time = time.time()
print(myLCS(w1,w2,len(w1),len(w2)))
print ("Time taken for non-memoized function was ", \
                (time.time() - start_time)," seconds.")