 # LCS Problem Revisited

Hey guys,
i recently went through the LCS PROBLEM REVISITED turorial thats been up in the tutorials section…
I was pretty much able to understand everything clearly, but this one part still seems obscure…

about counting the no of LCS in the given two strings…
this is a part of the code given in the tutorial for counting the no of distinct LCS…

if (lcs[x][y] == lcs[i][j] - 1) {
lcscount[i][j] = (lcscount[i][j] + lcscount[x][y])%23102009;
}

I’m not able to understand this particular part !!
if someone make things a little bit clear It’ll be very helpful thanks ! Remember : because of the initial problem, the three DP conditions are starting from the end of both strings.

Thus, we have to consider doing the calculations by analyzing the suffixes.

``````.
// checking if the length of the new subsequence is increased by
// one, as we only add one character (the k one). could be written
// lcs[i][j] == lcs[x][y] + 1 instead.

if (lcs[x][y] == lcs[i][j] - 1)
{
// at the i,j position, we add the number of distinct suffix
// subsequences starting with the k letter (lcscount[x][y])
// it could be written lcscount[i][j] += lcscount[x][y] but
// an overflow could occur. then, we take the modulo right now.

lcscount[i][j] = (lcscount[i][j] + lcscount[x][y])%23102009;
}

/*
example with i=6, j=1, and k='a'

0 1 2 3 4 5 6 7 8 9 ... M-1
|-------------------------|
string1 |a|b|c|d|e|d|c|b|d|a|b|e|e|
|-------------------------|
i     x

0 1 2 3 4 5 6 7 8 N-1
|-------------------|
string2 |a|b|d|a|e|e|d|c|b|a|
|-------------------|
j   y
*/``````
2 Likes

Thanks mate !! that really helped !

no problem, was glad to help 1 Like

@cyberax , man one more clarification !, what does lcscount contain initially ? i mean “lcscount[i][j] = (lcscount[i][j] + lcscount[x][y])%23102009;” keeps adding only zeroes right ?? and the result is going to be zero eventually…or am i missing some key point here ?

yeah, the tutorial is quite buggy… actually you could have a look at this. it’s the author’s solution. in the solve() function, the lcscount[][] array from the tutorial is the next[][][k] array from the code. the missing part is the recursive call. Ahh, just what i was looking for thanks ! now clear !

//