# Longest common sequence matrix giving wrong answer

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

I built this matrix for my case

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)

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]