Dynamic Programming:Longest Common Subsequence

QUESTION

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.

ANSWER

#include <stdio.h>
#include<string.h>
//#include<stdc++.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);
   else
     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";
 scanf("%s",X);
  scanf("%s",Y);
  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.

Powered By
CHP Adblock Detector Plugin | Codehelppro