0
$\begingroup$

I've implemented longest common substring in python. I know the usual way to reconstruct the path. But, I am reading my algorithm many times, I don't understand why it doesn't work for some test-cases. I am trying to construct the solution while the longest path is being made through dynamic programming.

def lcs(s1, s2):
    n = len(s1)
    m = len(s2)
    
    trow = [0] * (m+1)
    table = [trow] * (n+1)
    
    srow = [""] * (m+1)
    solution = [srow] * (n+1)
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[j-1]:                
                table[i][j] = table[i-1][j-1] + 1
                
                # Adding this character to the solution
                solution[i][j] = solution[i-1][j-1] + s1[i-1]
            
            elif table[i][j-1] > table[i-1][j]:
                table[i][j] = table[i][j-1]
                
                # Choosing the solution related to the longer path
                solution[i][j] = solution[i][j-1] 
                
            else:
                table[i][j] = table[i-1][j]
                
                # Choosing the solution related to the longer path
                solution[i][j] = solution[i-1][j] 
    
    return solution[n-1][m-1]
lcs('amin', 'kahmjiknln')
# Returns 'amin'

lcs('amin', 'aaaakahmjiknln')
# Returns 'aaaaamin'
$\endgroup$
1
  • 1
    $\begingroup$ Debugging or diagnosing problems with your code is off-topic here. We're not a coding site. Questions about algorithms can be on-topic, but we discourage questions written in code, as not everyone understands Python, and our focus is on the algorithm not on the implementation. $\endgroup$ – D.W. Feb 28 at 1:31
1
$\begingroup$

Lets deal with the issues one at a time, since there are a few of them.

Problem 1

Take a look at those lines of code:

trow = [0] * (m+1)
table = [trow] * (n+1)
    
srow = [""] * (m+1)
solution = [srow] * (n+1)

The problem with this code, is that the same list is being placed a few times. This means, that every list in $table$ must be all identical to $trow$ at all times. By changing one of the values in there, it will change all of them. For example, if $m=n=1$, then table == [[0,0],[0,0]]. Now, assume we somehow did this update: table[0][1] = 9. Then, we will have table == [[0, 9], [0, 9]] since $table$ contains the same list twice. This is essentially caused because lists are just pointers, and thus if you just copy the value in them it will just copy the pointer. A similar behavior can be seen in this code:

a = 5 # a == 5
b = a # a == 5, b == 5
b = 10 # a == 5, b == 10

A = [0, 1] # A == [0, 1]
B = A # A == [0, 1], B == [0, 1], A is B
B[0] = 9 # A == [9, 1], B == [9, 1], A is B

Here, the same thing happened: $a$ is not a list and therefore was copied as expected, but $A$ is a list and thus only the pointer to it was copied to $B$. A change in $B$ changed $A$ as well.

Back to your question. How to fix it, you ask? Like so:

table = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

solution = [["" for _ in range(m + 1)] for _ in range(n + 1)]

Problem 2

You have a slight problem with the indices. Since $solution$ is an $(n+1)$-by-$(m+1)$ matrix, you want solution[n][m] instead of solution[n - 1][m - 1]

$\endgroup$
1
$\begingroup$

Programming questions are off-topic here. Anyway your matrices table and solution are not properly initialized as they contain references to the same objects. Try:

    table = [[0]*(m+1) for j in range(n+1)]
    solution = [ ["" for i in range(m+1)] for j in range(n+1) ]

Moreover, the returned string should be solution[n][m] and not solution[n-1][m-1].

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.