LCS_example.cpp

/*
Arif Hosan
AIUB, CSE
*/
#include<iostream>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#define PI 2*acos(0.0)
#define SIZE 1000000
#define endl '\n'
int caseno=1;
#define CP() printf("Case %d: ",caseno++)
#define R() freopen("in.txt","r",stdin)
#define W() freopen("out.txt","w",stdout)
#define sfi(_i) scanf("%d",&_i)
#define sfc(_c) scanf("%c",&_c)
#define pf1(_i) cout<<_i
#define pfl() cout<<endl
#define pfs() printf(" ")
#define FOR(i,a,b) for(i=(a);i<(b);i++)
#define REV(i,a,b) for(i=(a);i>=(b);i--)
using namespace std;

int V[20][20];
char D[20][20];
stack<char>S;
void LCS(string,string);
void direction(string,string);

int main() {
    string a="ATGCTGAC", b="ATAGTATC";
    //cin>>a>>b;
    LCS(a,b);
    cout<<V[a.size()][b.size()];
    pfl();
    direction(a,b);
    while(!S.empty()) {
        cout<<S.top();
        S.pop();
    }
	return 0;
}


void LCS(string a,string b) {
    int a_s=a.size(), b_s=b.size();
    int i,j;
    int m=max(a_s,b_s);
    FOR(i,0,m+1) {
        V[0][i]=V[i][0]=0;
        D[0][i]=D[i][0]='0';
    }
    FOR(i,1,a_s+1) {
        FOR(j,1,b_s+1) {

            if(a[i-1]==b[j-1]) {
                V[i][j]=V[i-1][j-1]+1;
                D[i][j]='D';
            }
            else {
                m=max(V[i-1][j],V[i][j-1]);
                if(m==V[i-1][j]) D[i][j]='U';
                else D[i][j]='L';
                V[i][j]=m;
            }
            //cout<<i<<' '<<j<<' '<<V[i][j]<<' '<<a[i-1]<<' '<<b[j-1]<<" "<<m<<endl;
        }
    }
}

void direction(string a,string b) {
    int i=a.size(),j=b.size();
    while(i && j){
        if(D[i][j]=='L') j--;
        else if(D[i][j]=='U') i--;
        else {
            //cout<<i<<' '<<j<<' '<<a[i-1]<<endl;
            S.push(a[i-1]);
            i--;
            j--;
        }
    }
}