最长公共子序列实现
参考算法导论第208页
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void LCS(char *p,char *q)
{
int lenP,lenQ;
int *s,*t;
lenP=strlen(p);
lenQ=strlen(q);
int i,j;
if((s=(int*)malloc(sizeof(int)*(lenP+1)*(lenQ+1)))==NULL)
{
perror("malloc error");
exit(1);
}
if((t=(int*)malloc(sizeof(int)*(lenP+1)*(lenQ+1)))==NULL)
{
perror("malloc error");
exit(1);
}
for(i=0;i<(lenP+1);i++)
s[i]=0;
for(i=0;i<(lenQ+1);i++)
s[i*(lenP+1)]=0;
for(i=1;i<(lenQ+1);i++)
{
for(j=1;j<(lenP+1);j++)
{
if(q[i-1]==p[j-1])
{
s[i*(lenP+1)+j]=s[(i-1)*(lenP+1)+j-1]+1;
t[i*(lenP+1)+j]=3;
}else if(s[(i-1)*(lenP+1)+j]<s[i*(lenP+1)+j-1]){
s[i*(lenP+1)+j]=s[i*(lenP+1)+j-1];
t[i*(lenP+1)+j]=1;
}else{
s[i*(lenP+1)+j]=s[(i-1)*(lenP+1)+j];
t[i*(lenP+1)+j]=2;
}
}
}
/*输出矩阵结果*/
printf("output the result:\n");
for(i=0;i<(lenQ+1);i++)
{
for(j=0;j<(lenP+1);j++)
{
printf("%d ",s[i*(lenP+1)+j]);
}
printf("\n");
}
printf("output the result 箭头 1表示向左，2表示向上，3表示斜向上:\n");
for(i=0;i<(lenQ+1);i++)
{
for(j=0;j<(lenP+1);j++)
{
printf("%d ",t[i*(lenP+1)+j]);
}
printf("\n");
}
i=lenQ;
j=lenP;
/*倒序输出LCS*/
printf("倒序输出LCS\n");
while(i>1 || j>1)
{
if(t[i*(lenP+1)+j]==3)
{
printf("%c ",p[j-1]);
i--;
j--;
}else if(t[i*(lenP+1)+j]==2)
{
i--;
}else
j--;
}
printf("\n");
}
int main()
{
char *p="BDCABA";
char *q="ABCBDAB";
LCS(p,q);
}