动态规化算法之最长公共子序列

/*
 * Filename: comm_sub_list.c
 *
 * Function: 找出两个数组的最长公共子序列
 *
 * Note: 打印的时候是按逆序打印的
 *
 * Version: 1.0
 * Author:  WUSW
 * Date:    2009.4.21
 */
#include

#define ROW 7
#define COL 6

/* 主要用于处理边界情况 */
int getm(int m[ROW][COL], int i, int j)
{
  if (i<0 || j<0)
    {
      return 0;
    }
  return m[i][j];
}

/* m[i][j]存贮x[i]到y[j]最长公共子序列的长度，s存贮的是它们的来源，以供回溯 */
void comm_lgest_sub_list( const int *x, const int lenx,
              const int *y, const int leny,
              int m[ROW][COL], int s[ROW][COL] )
{
  int i = 0;
  int j = 0;
 
  for (i=0; i    {
      for (j=0; j    {
      m[i][j] = 0;
      s[i][j] = 0;
    }
    }

  for (i=0; i    {
      for (j=0; j    {
      if (x[i] == y[j])
        {
          m[i][j] = getm(m, i-1, j-1) + 1;
          s[i][j] = 0;
        }
      else if(getm(m, i-1, j) >= getm(m, i, j-1))
        {
          m[i][j] = getm(m, i-1, j);
          s[i][j] = 1;
        }
      else
        {
          m[i][j] = getm(m, i, j-1);
          s[i][j] = 2;
        }
    }
    }
}

/* 逆序输出最长公共子序列 */
void print_comm_sub_list( const int *x,  int i, int j, int s[ROW][COL] )
{
  while (i>=0 && j>=0)
    {
      if (0 == s[i][j])
    {
      printf( "%d ", x[i] );
      i--;
      j--;
    }
      else if(1 == s[i][j])
    {
      i--;
    }
      else if(2 == s[i][j])
    {
      j--;
    }
    }
  printf( "\n" );
}
   
 
int main(int argc, char * argv[])
{
  int x[] = {1, 2, 3, 4, 4, 1, 2};
  int y[] = {2, 3, 1, 2, 3, 4};

  int m[ROW][COL] = {{0}};
  int s[ROW][COL] = {{0}};
 
  comm_lgest_sub_list( x, ROW, y, COL, m, s );
  print_comm_sub_list( x, ROW-1, COL-1, s );
 

  return 0;
}