First, I wanna say sorry for my awful English!
These days, i start to learning algorithms, and now i want to count the LCS of the two strings.
I wrote my code and sent it to the online judge, but it always got WA. I can find what’s wrong with it, because it succeed int my computer. I need your help, although it’s a very simple question, but i am a newbie, so i ask this question.
Here is my core code.
string first, second;
cin >> first >> second;
int n = first.length(), m = second.length();
for(int i = 0; i <= m; i++) lcs[i][0] = 0;
for(int j = 0; j <= n; j++) lcs[0][j] = 0;
// index from 1 to n for
for(int i = n; i >= 1; i--) first[i] = first[i-1];
for(int j = m; j >= 1; j--) second[j] = second[j-1];
for(int r = 1; r <= m; r++){
for(int c = 1; c <= n; c++){
if(first[c] == second[r]) lcs[r][c] = lcs[r-1][c-1] + 1;
else lcs[r][c] = max(lcs[r-1][c], lcs[r][c-1]);
}
}
printf("%d\n", lcs[m][n]);
}
}
Thanks a lot for helping me with such a simple question!