Longest Common Subsequence

lcs.py

#!/usr/bin/python2
#
# Longest Common Subsequence problem
#      Just implements simple lcs function. One solution, not all.

def lcs(x, y):
    if len(x) == 0 or len(y) == 0:
        return ""
    elif x[-1:] == y[-1:]:
        return lcs(x[:-1], y[:-1]) + x[-1:]
    else:
        a = lcs(x, y[:-1])
        b = lcs(x[:-1], y)

        if len(a) > len(b):
            return a
        else:
            return b

# input

x = raw_input("Enter first string :  ")
y = raw_input("Enter second string:  ")

print "LCS = ", lcs(x, y)