Longest Common Subsequence

Longest Common Subsequence.cpp

#include <iostream>

#include <fstream>

#include <math.h>

#include <string>

#define UP 0

#define LEFT 1

#define MATCH 2

using namespace std;

int mat[100][100];

int c[100][100];

int b[100][100];

std::string x;

std::string y;

void lenlen()

{

//int &ref = cache[]

for(int i = 0; i <= x.length(); i ++)

{

c[i][0] = 0;

}

for(int i = 0; i <= y.length(); i ++)

{

c[0][i] = 0;

}

for(int i = 1; i <= x.length(); i ++)

{

for(int j = 1; j <= y.length(); j ++)

{

if(x[i - 1] == y[j - 1])

{

c[i][j] = c[i - 1][j - 1] + 1;

b[i][j] = MATCH;

}

else if(c[i - 1][j] > c[i][j - 1])

{

c[i][j] = c[i - 1][j];

b[i][j] = UP;

}

else

{

c[i][j] = c[i][j - 1];

b[i][j] = LEFT;

}

}

}

}

void print(int i, int j)

{

if(i == 0 && j == 0)

return;

if(i < 0 || j < 0)

return;

if(b[i][j] == MATCH)

{

print(i - 1, j - 1);

cout << x[i - 1];

}

else if(b[i][j] == UP)

{

print(i - 1, j);

}

else

print(i, j - 1);

}

int main()

{

fstream fin("input.txt");

int n, m;

fin >> n >> m;

fin >> x >> y;

lenlen();

cout << c[n][m] << endl;

print(n, m);

}