Advertisement
apl-mhd

DP Longest Common Subsequence

Mar 1st, 2018
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 0.97 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6.  
  7. void printMatrix(int mat[7][6], int row, int col){
  8.  
  9.  
  10.  
  11.  
  12.     for(int i=0; i<row; i++){
  13.  
  14.         for(int j=0; j<col; j++){
  15.  
  16.            cout<<mat[i][j]<<" ";
  17.             //mat[i][j]=0;
  18.         }
  19.         cout<<endl;
  20.     }
  21.  
  22.  
  23. }
  24.  
  25.  
  26.  
  27. int main() {
  28.  
  29.  
  30.     char row[] = {'a','b','c','d','a','f'};
  31.     char col[] = {'a','c','b','c','f'};
  32.  
  33.  
  34.  
  35.     int rowSize = sizeof(row)/ sizeof(char);
  36.     int colSize = sizeof(col)/ sizeof(char);
  37.  
  38.     int t[7][6];
  39.  
  40.  
  41.     for (int i = 0; i <= 6 ; ++i) {
  42.         for (int j = 0; j <=5 ; ++j) {
  43.  
  44.             if(i==0 || j == 0) {
  45.                 t[i][j] = 0;
  46.  
  47.                 continue;
  48.             }
  49.  
  50.             if(row[i-1] == col[j-1]){
  51.  
  52.                 t[i][j] = t[i-1][j-1] +1;
  53.  
  54.             } else{
  55.  
  56.                 t[i][j] = max(t[i][j-1], t[i-1][j]);
  57.  
  58.  
  59.             }
  60.  
  61.         }
  62.  
  63.     }
  64.  
  65.     printMatrix(t, 7,6);
  66.  
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement