longest common subsequence

<input>

m n

a

b

54 98 

bnbaqclwzrfkbskuwydbufxlagfgzmfwysjigulxraxrbxwnazupop 

bsxicfbinhukhpunbcqnabqwbrnndwdgiwiskjbumjbwllcdddlleszybrrcntaecwtgcedpnapadfasxfnayogugndwyksije

<output>

22

bnbaqwrkbuwydfxaggwys

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define left 1

#define up 2

#define dagak 3

char a[1000];

char b[1000];

int c[100][100];

int dir[100][100];

int n,m;

void printlcs(int dir[100][100], char* a, int i,int j)

{

if (i==0 || j==0)

return;

if (dir[i][j] == dagak)

{

printlcs(dir,a,i-1,j-1);

printf ("%c",a[i]);

}

else if (dir[i][j] == up)

{

printlcs(dir,a,i-1,j);

}

else if (dir[i][j] == left)

{

printlcs(dir,a,i,j-1);

}

}

int main(void)

{

int i,j;

int logn;

// n

// nxn matrix

FILE* f = fopen ("input2.txt","r");

fscanf (f,"%d %d\n",&m,&n);

fgets(a+1,sizeof(a),f);

fgets(b+1,sizeof(b),f);

for (i=0;i<m;i++){

c[i][0] = 0;}

for (i=0;i<n;i++){

c[0][i] = 0;}

for (i=1;i<=m;i++)

{

for (j=1;j<=n;j++)

{

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

{

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

dir[i][j] = dagak;

}

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

{

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

dir[i][j] = up;

}

else

{

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

dir[i][j] = left;

}

}

}

printf ("%d\n",c[m][n]);

printlcs(dir,a,m,n);

printf ("\n");

}