Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.7 kB
1
Indexable
Never
#include<bits/stdc++.h>
using namespace std;

int main(){
    string seq1, seq2;
    cout << "Enter the sequences: ";
    cin >> seq1 >> seq2;

    int n = seq1.size(), m = seq2.size();

    int ar[n+1][m+1];
    char track[n+1][m+1];

    for(int i=0; i<=n; i++)
        ar[i][0] = 0;
    for(int j=0; j<=m; j++)
        ar[0][j] = 0;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(seq1[i-1] == seq2[j-1]){
               ar[i][j] = ar[i-1][j-1] + 1;
               track[i][j] = 'D';
            }
            else{
                if(ar[i-1][j] >= ar[i][j-1]){
                    ar[i][j] = ar[i-1][j];
                    track[i][j] = 'U';
                }
                else{
                   if( ar[i][j] = ar[i][j-1]){
                        track[i][j] = 'L';
                   }
                }
            }
        }
    }

    cout << "Length of the LCS: " << ar[n][m] <<endl<<endl;
    
    int i=n, j=m;
    vector<char>v;
    while(i>0 && j>0){
        if(track[i][j] == 'D'){
            v.push_back(seq1[i-1]);
            i--;
            j--;
        }
        else if(track[i][j] == 'U'){
            i--;
        }
        else{
            j--;
        }
    }

    reverse(v.begin(), v.end());
    for(int i=0; i<v.size(); i++){
        cout << v[i];
        }
    cout << endl<<endl;


    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
            cout << ar[i][j] << " ";
            }
        cout << endl;
    }
    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
            cout << track[i][j] << " ";
            }
        cout << endl;
    }
    return 0;
}
Leave a Comment