printing the LCS - longest common subsequence

[tubby123]

guys, i am having trouble printing the LCS.
This is the algorithm i am following to get the count of the LCS.

int main(void)
{
  printf("\nThe LCS is %d",LCS(0,0));


}

int LCS(int m, int n)
{
   if(m==l1 || n==l2)
      return 0;
   
   if(X[m] == Y[n])
      return 1 + LCS(X[m+1],Y[n+1]);
   else 
      return max( LCS(X[m],Y[n+1], LCS(X[m+1],Y[n]));
}

Now where do i put a printf ????
I tried putting at the line where both are equal, ie, if(X[m] == Y[n]), but obviously it doesnt work...

[griswolf]

In your main() function, call lcs = LCS(m,n); // where did m and n come from? then print that value.

[tubby123]

no i am going from front-to-end rather than from back to end.
Thats why i have passed as LCS(0,0)

[griswolf]

Umm. The point of a function call is to get the answer, and if the function is recursive, then you still want to get the answer to the initial call. You appear to be wanting to debug the recursion? I do see that you are starting at (0,0) but that is just "leftmost part of each array". The "normal" way to do this kind of recursion is two write two functions: The public function takes two strings, and calls the recursive function starting at 0,0. This is called separation of concerns: Internally, you care about the way the string is encoded, but externally, your user doesn't need to care about that. If the encoding changes (maybe the strings are compressed, or stored as an array of arrays of char, or maybe in a multi-byte encoding) then you only rewrite the underlying "worker" part of the function, the externally visible part stays the same.

Also, I'm not convinced your code works as intended. What is X in your code? You are coding as if it is an array; but treating it as a pointer. This is legal in C, but not always in other languages. If this is a C question, you are in the wrong forum, and should be here.

[TrustyTony]

Dynamic programming worked for me in Python, I am not sure how efficient you can make your recursive algorithm, probably need memoized function to approach dynamic programming approach. Looks like you want to find the length of the common sequence only.

[Momerath]

What is X in your code?

I'd question the use of global values X, Y, l1, and l2 (that is a lower case L). While this function might work for one specific example, it's not very reusable and poorly designed.