1
$\begingroup$

I am trying to find longest common sequence for these two strings

SHINCHAN
NOHARAAA

The common sequence is NHA of length 3

But when I am trying to find out this through LCS matrix which I learnt from this link https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Based on the explanation and this example given there

enter image description here

I built this matrix for my case

enter image description here

But my matrix is reaching to the length 6 while it should reach to length 3 only because that is the longest comment sequence of the two strings I am using.

Could anybody please point out the mistake I am doing? I can see the problem is happening because of the extra 3 A's at the end of one of the string.

$\endgroup$
1
$\begingroup$

Look at row=1 and column=8 (using 0 indexed numbers) in your matrix. That value says that the length of LCS between SHINCHAN and N is 2, which is impossible since N itself is of size 1.

When s1[i] and s2[j] are equal you need to look at the number in matrix[i-1][j-1] and add one and not matrix[i][j-1] (which I think you are doing). You can compare your method to the pseudocode written in the wikipedia article to arrive at the correct matrix (copied below for convenience)

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]
$\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.