最长公共子序列

最长公共子序列:
百度百科定义如下：一个数列 ，如果分别是两个或多个已知的子序列，且是所有符合此条件序列中最长的，则 称为已知序列的最长公共子序列。
递推关系如下：

其中c[i,j]记录Xi与Yj的最长公共子序列。
代码实现如下
#include
#include
#include
#include
enum dir{Kinit = 0,Kleft,Kup,Kleftup};
void printLcs(int **direction,char *str1,char *str2,int,int);
int  lcs(char *str1,char *str2)
{
if (str1 == NULL || str2 == NULL)
return ;
int len1 = strlen(str1);
int len2 = strlen(str2);
int i = 0,j = 0;
int **lcs_length;
lcs_length = (int **)malloc(sizeof(int)*len1);
for (i = 0;i < len1;i++)
{
lcs_length[i] = (int *)malloc(sizeof(int)*len2);
}
for (i = 0;i < len1;i++)
{
for (j = 0;j < len2;j++)
{
lcs_length[i][j] = 0;
}
} 
int **direction;
direction = (int **)malloc(sizeof(int)*len1);
for (i = 0;i < len1;i++)
{
direction[i] = (int *)malloc(sizeof(int)*len2);
}
for (i = 0;i < len1;i++)
{
for (j = 0;j < len2;j++)
{
direction[i][j] = 0;
}
}
for (i = 0;i < len1;i++)
{
for (j = 0;j < len2;j++)
{
if (i == 0 || j == 0)
{
if (str1[i] == str1[j])
{
lcs_length[i][j] = 1;
direction[i][j] = Kleftup;
}
else
{
if (i > 0)
{
lcs_length[i][j] = lcs_length[i-1][j];
direction[i][j] = Kup;
}
if (j > 0)
{
lcs_length[i][j] = lcs_length[i][j-1];
direction[i][j] = Kleft;
}
}
}
else if (str1[i] == str2[j])
{
lcs_length[i][j] = lcs_length[i-1][j-1]+1;
direction[i][j] = Kleftup;
}
else if (lcs_length[i-1][j] > lcs_length[i][j]-1)
{
lcs_length[i][j] = lcs_length[i-1][j];
direction[i][j] = Kup;
}
else
{
lcs_length[i][j] = lcs_length[i][j-1];
direction[i][j] = Kleft;
}

}
}
printLcs(direction,str1,str2,len1-1,len2-1);
for (i = 0;i < len1;i++)
free(lcs_length[i]);
free(lcs_length);
for (i = 0;i < len1;i++)
free(direction[i]);
free(direction);
return lcs_length[len1-1][len2-1];
}
void printLcs(int **direction,char *str1,char *str2,int rows,int cols)
{
if (str1 == NULL || str2 == NULL)
return ;
int size1 = strlen(str1);
int size2 = strlen(str2);
if (size1 == 0 || size2 == 0 || !(rows < size1 && cols < size2))
return ;
if (direction[rows][cols] == Kleftup)
{
if (rows > 0 && cols > 0)
printLcs(direction,str1,str2,rows-1,cols-1);
printf("%c",str1[rows]);
}
else if (direction[rows][cols] == Kleft)
{
if (cols > 0)
printLcs(direction,str1,str2,rows,cols-1) ;
}
else
{
if (rows > 0)
printLcs(direction,str1,str2,rows-1,cols);
}
}
int main()
{
char str1[1024];
gets(str1);
char str2[1024];
gets(str2);
int result = lcs(str1,str2);
printf("最长公共自序列是:%d\n",result);
return 0;
}

执行结果如下（centos5.5）
[root@localhost 21212]# ./a.out
gho
hlo
go最长公共自序列是:2