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…
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
*/
@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.
thanks ! now clear !