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


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.


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)

    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]
    return C[m,n]

Your Answer

