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 ! :slight_smile:

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 :slight_smile:

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. :slight_smile:

Ahh, just what i was looking for :smiley: thanks ! now clear !