Length of Longest Common sequence Python recursive function

Question

I am trying to implement this function with recursion in python and I have a mistake. I can't understand what is the mistake, could you help me?

The code:

def LongestCommonSubsequence(X,Y,tailX,tailY):
    if tailX == tailY and tailX!='' and (X=='' or Y==''):
            return len(tailX)
    elif X=='' or Y=='':
            return 0
    else:

        return max( LongestCommonSubsequence(X[1:],Y[1:],tailX+X[0],tailY+Y[0]),
                    LongestCommonSubsequence(X[1:],Y[1:],tailX+X[0],tailY),
                    LongestCommonSubsequence(X[1:],Y[1:],tailX,tailY+Y[0]),
                    LongestCommonSubsequence(X[1:],Y[1:],tailX,tailY)) 

X=raw_input() 
Y=raw_input() 
print LongestCommonSubsequence(X,Y,'','')

input:

abccdabab 
bacdbeb 

expected output:5
what i get:4

Answer 1

You appear to be trying to optimise for common tail strings here; if both strings end with the same tail you can indeed skip a few recursion steps.

But you are not actually building a tail, you are building the head, the characters at the start.

Here is a working recursive llcs without that optimisation:

def llcs(xstr, ystr):
    if not xstr or not ystr:
        return 0
    x, xtail, y, ytail = xstr[0], xstr[1:], ystr[0], ystr[1:]
    if x == y:
        return 1 + llcs(xtail, ytail)
    return max(llcs(xstr, ytail), llcs(xtail, ystr))

This finds the maximum longest common substring length by comparing lengths found for removing a character from the start of either xstr or ystr, not both.

Your code specifically never pairs up X with Y[1:] or X[1:] with Y for the max() call, so you never will find an LCS for that specific starting character in either X or Y.

You can then try and optimise by looking at xtail and ytail (actual tails) and bail out early:

def llcs(xstr, ystr):
    if not xstr or not ystr:
        return 0
    x, xtail, y, ytail = xstr[0], xstr[1:], ystr[0], ystr[1:]
    if x == y:
        if xtail == ytail:
            # if the tails match, bail out early
            return 1 + len(xtail)
        return 1 + llcs(xtail, ytail)
    return max(llcs(xstr, ytail), llcs(xtail, ystr))