最长公共子序列

最长公共子序列

            0                        i==0 || j==0

 c[i,j] =  c[i-1,j-1] + 1            str1[i] == str2[j]

           max(c[i-1,j],c[i,j-1])    str1[i] != str2[j]

 

lcs(序列)最大的难点是打印子序列,这里这个二维指针传值传半天没搞明白,用数组指针,但是要已知数组大小就好了,我这里搞成全局的了

 

#include <stdio.h>
#include <stdlib.h>

char b[10][10];

void print_lcs( char* str, int i, int j)
{
    if(i==0 || j == 0)
       return;
    if( b[i][j] == 'a')
      {
        print_lcs(str, i-1, j-1);
        printf("%c",str[i-1]);
      }
     else if( b[i][j] == 'u' )
        print_lcs( str, i-1, j);
     else
        print_lcs( str, i, j-1);
}

void count_lcs(char* str1,char* str2)
{
  int len1 = strlen(str1);
  int len2 = strlen(str2);
  int i;
  int j;
  int c[len1+1][len2+1];
  
  for(i=0;i<len1+1;i++)
     c[i][0] = 0;
     
   for(j=0;j<len2+1;j++)
    c[0][j] = 0;
  
   for(i=1;i<len1+1;i++)
   {
     for(j=1;j<len2+1;j++)
     {
       if(str1[i-1] == str2[j-1])
        {
          c[i][j] = c[i-1][j-1]+1;
          b[i][j] = 'a';
        }
       else if(c[i-1,j]>=c[i,j-1])
        {
          c[i][j] = c[i-1][j];
          b[i][j] = 'u';
         }
       else
        {
         c[i][j] = c[i][j-1];
         b[i][j] = 'l';
        }
     }
   }
   
   printf("lcs ok\n");
  // int (*d)[len2+1] = b;

   
   print_lcs( str1, len1, len2);
   printf("\n");
}

int main(int argc, char *argv[])
{
  char* str1 = "abcbdabc";
  char* str2 = "bdcabac";
  
  printf("str1:%s\nstr2:%s lcs is:\n", str1, str2);
  count_lcs(str1,str2);
  system("PAUSE");    
  return 0;
}