LCS as per done in LAB

lcs.cpp

#include<iostream>
using namespace std;

void LCS_Length(char*,char*,int,int);

int c[100][100];
string b[100][100];

void Print_LCS(string b[][100],string x,int i,int j){
    //cout<<i<<" "<<j;

    if(i == 0 || j == 0){
        return;
    }
    if(b[i][j] == "copy"){
        Print_LCS(b,x,i-1,j-1);
        cout<<x[i]<<" ";
    }
    else if(b[i][j] == "skipX"){
        Print_LCS(b,x,i-1,j);
    }else{
        Print_LCS(b,x,i,j-1);
    }
}

int main(){

    /*
    string x = " ABBCCDC";
    string y = " ACCBBDCB";
    int len_x = x.length();
    int len_y = y.length();
    */


    int len_x,len_y;
    cout<<"X length: "<<endl;
    cin>>len_x;
    cout<<"Y length: "<<endl;
    cin>>len_y;

    char x[len_x + 1];
    char y[len_y + 1];

    cout<<"X: ";
    for(int i=1;i<=len_x;i++){
        cin>>x[i];
    }
    cout<<"Y: ";
     for(int i=1;i<=len_y;i++){
        cin>>y[i];
     }



    LCS_Length(x,y,len_x,len_y);

    cout<<endl;
    //test print
    for(int i=1;i<len_x;i++){
        for(int j=1;j<len_y;j++){
            cout<<b[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;

    Print_LCS(b,x,len_x,len_y);

}



void LCS_Length(char* x,char* y,int len_x,int len_y){

    for(int i=1;i<=len_x;i++){
        c[i][0] = 0;
    }

    for(int j=0;j<=len_y;j++){
        c[0][j] = 0;
    }

    for(int i=1;i<=len_x;i++){
        for(int j=1;j<=len_y;j++){
            if(x[i] == y[j]){
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = "copy";
            }
            else if(c[i-1][j] >= c[i][j-1]){
                c[i][j] = c[i-1][j];
                b[i][j] = "skipX";
            }else{
                c[i][j] = c[i][j-1];
                b[i][j] = "skipY";
            }
        }
    }

    //test print
    cout<<c[len_x][len_y]<<endl;

    //backtrack

}