Dynamic Programming:Longest Common Subsequence


LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. \n\nA subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. \n\nFor example, \”abc\”, \”abg\”,\”bdf\”, \”aeg\”, \”acefg\”, .. etc are subsequences of \”abcdefg\”. \n\nSo a string of length n has 2^n different possible subsequences.


#include <stdio.h>
int max(int a, int b);
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
   if (m == 0 || n == 0)
     return 0;
   if (X[m-1] == Y[n-1])
     return 1 + lcs(X, Y, m-1, n-1);
     return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
/* Utility function to get max of 2 integers */
int max(int a, int b)
    return (a > b)? a : b;
/* Driver program to test above function */
int main()
  char X[10],Y[10]; int m,n;
  //char X[] = "AGGTAB";
  //char Y[] = "GXTXAYB";
  m = strlen(X);
  n = strlen(Y);
  printf("Length of LCS is %d", lcs( X, Y, m, n ) );
  return 0;
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.