jain12

longest common subsequence by dp

May 4th, 2020
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.67 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstring>
  3. #include<math.h>
  4. using namespace std;
  5.  
  6. int LCS(char str1[],char str2[],int l1,int l2){
  7.   if(l1==0 ||l2==0)
  8.     return 0;
  9.   int arr[l1+1][l2+1];
  10.   for(int i=0;i<=l1;i++){
  11.     for(int j=0;j<=l2;j++){
  12.       if(i==0 || j==0)
  13.         arr[i][j]=0;
  14.       else{
  15.           if(str1[i-1]==str2[j-1])
  16.             arr[i][j]=1+arr[i-1][j-1];
  17.           else
  18.             arr[i][j]=max(arr[i][j-1],arr[i-1][j]);
  19.           }
  20.       }
  21.     }
  22.     return arr[l1][l2];
  23.   }
  24.  
  25. int main(){
  26.   char X[] = "AGGTAB";
  27.   char Y[] = "GXTXAYB";
  28.   int m = strlen(X);
  29.   int n = strlen(Y);
  30.   cout<<"Length of LCS is "<<LCS( X, Y, m, n ) ;
  31.   return 0;
  32.   }
Add Comment
Please, Sign In to add comment