Longest Common Subsequence

Longest Common Sub-Sequence


Idea behind the logic is

1. If the two string's first character is same then truncate both and use the truncated string and proceed.
2. if the first two character is not same then, first truncate one character from string s1 and call the function, then truncate the character from string s2 and call the function again. and take the max from that.
 

#include <stdio.h>
#include <strings.h>
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define MIN(x, y) (((x) < (y)) ? (x) : (y))

int lcs(char *s1, char *s2) {

 if (strlen(s1) == 0 || strlen(s2) == 0) 
  return 0;

 if (*s1 == *s2) {

  return 1+lcs(s1+1, s2+1);
 }
 else {

  return MAX(lcs(s1+1, s2), lcs(s1, s2+1));
 }
}

int main() {

 char s2[] = "abcd";
 char s1[] = "efgh";

 printf("%d\n", strlen(s2));

 int c = lcs(s1, s2);

 printf("%d   count = %d\n", c, count);
}