Untitled
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