You are viewing a single comment's thread. Return to all comments →
Another word for this is "longest common subsequence" (or lcs). The basic algorithm is
int lcs(char *s1, int i, char *s2, int j) { if (i == s1.length || j == s2.length) { return 0; } if (s1[i] == s2[j]) { return 1 + lcs(s1, i+1, s2, j+1); } return max(lcs(s1, i+1, s2, j), lcs(s1, i, s2, j+1); }
Called from main with
return lcs(s1, 0, s2, 0);
Of course, you will need to use memoization to avoid an exponential run time.
Seems like cookies are disabled on this browser, please enable them to open this website
Common Child
You are viewing a single comment's thread. Return to all comments →
Another word for this is "longest common subsequence" (or lcs). The basic algorithm is
Called from main with
Of course, you will need to use memoization to avoid an exponential run time.