Advertisement
Riz1Ahmed

Longest Common Subsequence

Feb 19th, 2019
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.48 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. int main(){
  6.     char a[]="abcb";
  7.     char b[]="bdcab";
  8.     int sa=strlen(a);
  9.     int sb=strlen(b);
  10.     int m[sa+2][sb+2],i,j;
  11.     memset(m,0,sizeof (m));
  12.     for (i=1; i<=sa; i++){
  13.         for (j=1; j<=sb; j++){
  14.             if (a[i-1]==b[j-1])
  15.                 m[i][j]=m[i-1][j-1]+1;
  16.             else
  17.                 m[i][j]=max(m[i-1][j],m[i][j-1]);
  18.         }
  19.     }
  20.     for (i=0; i<=sa; i++){
  21.         for (j=0; j<=sb; j++)
  22.             printf("%d ",m[i][j]);
  23.         printf("\n");
  24.     }
  25.     printf("%d\n",m[i-1][j-1]);
  26. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement