Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.8 kB
7
Indexable
#include<bits/stdc++.h>
using namespace std;

int main()
{
    string seq1, seq2;
    cout << "Enter the sequences: " << endl;
    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
                {
                    ar[i][j] = ar[i][j-1];
                    track[i][j] = 'L';
                }
            }
        }
    }

    cout << "Length of the LCS: " << ar[n][m] << 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;


    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;
}