LCS(Longest common subsequence) example code

원본 소스 : http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/ 

path finding 기능 추가

/* Dynamic Programming implementation of LCS problem */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int max(int a, int b);


/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( int **L, char *X, char *Y, int m, int n )
{
    int i, j;
    int a, b;

    /* Following steps build L[m+1][n+1] in bottom up fashion. Note
    that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
    for (i=0; i<m; i++)
    {
        for (j=0; j<n; j++)
        {
            if (i == 0 || j == 0){
                L[i][j] = 0;
            }else if (X[i-1] == Y[j-1]) {
                L[i][j] = L[i-1][j-1] + 1;
                printf("%c[%d]:%c[%d]=%d\n", X[i-1], i-1, Y[j-1], j-1, L[i][j] );
            }else{
                L[i][j] = max(L[i-1][j], L[i][j-1]);
            }
        }

    }

    /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
    printf("     ");
    for (i=0; i<m; i++)
        printf("%02d ", i );
    printf("\n");
    printf("     ");
    for (i=0; i<m; i++)
        printf("%02c ", X[i] );
    printf("\n");
    for( a = 0; a < n; a++ )
    {
        for( b = 0; b < m; b++ )
        {
            if( b == 0 ) printf("%02d %c ",a , Y[a] );
            printf("%02d ", L[b][a]);
        }
        printf("\n");
    }
    printf("\n");
    return L[m][n];
}

/* Utility function to get max of 2 integers */
int max(int a, int b)
{
    return (a > b)? a : b;
}


typedef struct node
{
    int x;
    int y;
    char type;
    char code;
    struct node *next;
}node_t;

node_t *make_node( char type, char code, int x, int y )
{
    node_t *node;
    node = malloc(sizeof(node_t));
    node->type = type;
    node->code = code;
    node->x    = x;
    node->y    = y;
    //printf("%d:%d=%c\n",x,y,code);
    return node;
}
int print_best_path( node_t *header )
{
    int x = 0;
    node_t *node, *pnode;
    node = header->next;
    pnode= node->next;
    while(  node != NULL )
    {
        printf("%02d:%02d\t%c\t%c\n", node->x, node->y, node->type, node->code );
        node = node->next;
    }
    return 0;
}


void free_node( node_t *header )
{
    node_t *node, *tnode;
    node = header->next;
    while(  node != NULL )
    {
        tnode = node;

        node = node->next;
        free( tnode );
    }
}

int find_best_path( int **L, char *X, char *Y, int m, int n, node_t *header )
{
    int i = m;
    int j = n;
    node_t *node;
    while( i > 0 && j > 0 )
    {
        if( X[i-1] == Y[j-1] ){
            node = make_node( '=', X[i-1], i-1, j-1 );
            node->next = header->next;
            header->next = node;
            j--;
            i--;
        }else{
                if( L[i-1][j] > L[i][j-1] )
                {
                    node = make_node( '-', X[i-1], i-1, j );
                    node->next = header->next;
                    header->next = node;
                    i--;
                }
                else
                {
                    node = make_node( '+', Y[j-1], i, j-1 );
                    node->next = header->next;
                    header->next = node;
                    j--;
                }
        }
    }
    while( i > 0 )
    {
        node = make_node( '-', X[i-1], i-1, j );
        node->next = header->next;
        header->next = node;
        i--;
    }
    while( j > 0 )
    {
        node = make_node( '+', Y[j-1], i, j-1 );
        node->next = header->next;
        header->next = node;
        j--;
    }
    return 0;
}
/* Driver program to test above function */
int main()
{
  char X[] = "Apples are a fruit";
  char Y[] = "Bananas are also fruit";
//  char X[] = "AGTAB";
//  char Y[] = "AGGTKACB";

  int len = 0, i;
  int m = strlen(X);
  int n = strlen(Y);
  int **L;
  node_t node = {0};
  L = malloc(sizeof(int*)*(m+1));
  for( i = 0; i  < m+1; i++ )
     L[i] = malloc(sizeof(int)*(n+1));

  len = lcs( L, X, Y, m, n );
  find_best_path( L, X, Y, m, n, &node );
  print_best_path( &node );
  free_node( &node );

//  getchar();
  return 0;
}