CODEWITHSUNDEEP
pythonlongest-substring
michael kova
michael kova

Reputation: 105

Length of Longest Common sequence Python recursive function

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

Upvotes: 1

Views: 1485

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1121346

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))

Upvotes: 2

Related Questions