读书人

求大神指点关于最大公共子序列程序!

发布时间: 2013-01-07 10:02:25 作者: rapoo

求大神指导,关于最大公共子序列程序!!
挑错挑了好久,但实在不懂哪里错了,代码如下~
说是内存溢出好像。。。

#include<stdio.h>
void LCSLength(int m,int n,char *x,char *y,int c[8][7],int b[8][7])
{
int i,j;
for(i=1;i<=m;i++) c[i][0]=0;
for(i=1;i<=n;i++) c[0][i]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(x[i]==y[j])
{c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}
else if(c[i-1][j]>=c[i][j-1])
{c[i][j]=c[i-1][j];b[i][j]=2;}
else {c[i][j]=c[i][j-1];b[i][j]=3;}
}
}

void LCS(int i,int j,char *x,int b[8][7] )
{
if(i==0||j==0) return;
if(b[i][j]==1){LCS(i-1,j-1,x,b);printf("%c",x[i]);}
else if(b[i][j]=2) LCS(i-1,j,x,b);
else LCS(i,j-1,x,b);
}
int main()
{
int c[8][7]={{0}};
int b[8][7]={{0}};
char X[8]={' ','A','B','C','B','D','A','B'};
char Y[7]={' ','B','D','C','A','B','A'};
LCSLength(8,7,X,Y,c,b);
printf("最大公共子序列长度为%d\n",c[7][6]);
LCS(7,6,X,b);
return 1;
}

[解决办法]
不看算法 数组访问越界了。。
[解决办法]
LCSLength(8,7,X,Y,c,b);
=>
LCSLength(7,6,X,Y,c,b);

else if(b[i][j]=2)
=>
else if(b[i][j]==2)
[解决办法]
//最长公共子序列字符个数
//c[i][j]保存字符串 {xi},{yj},(长度分别为i,j)的最长公共子序列的字符个数
//i=0或者是j=0 时,c[i][j]必定为零, i,j>=0 且 xi=yj, c[i][j]=c[i-1][j-1]+1
//若 i,j>0 但xi!=yj, c[i][j]=max{ c[i-1][j] , c[i][j-1] }
#include <stdio.h>
#include <string.h>
int c[1001][1001];
void lcs(int a, int b, char x[], char y[], int c[][1001]) {
int i,j;
for(i=1;i<a;i++)
c[i][0]=0; //if b==0, set c[i][j]=0;
for(i=1;i<b;i++)
c[0][i]=0; // if a==0; set c[i][j]=0;
for(i=1;i<=a;i++) // if a!=0,b!=0 loop
for(j=1;j<=b;j++) {
if(x[i-1]==y[j-1])
c[i][j]=c[i-1][j-1]+1;
else if (c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
}
}


int main() {
char x[1001],y[1001];
while ( scanf("%s%s",x,y)!=EOF ) {
int a=strlen(x);
int b=strlen(y);
memset(c,0,sizeof(c));
lcs(a,b,x,y,c);
printf("%d\n",c[a][b]);
}
return 0;
}

读书人网 >C语言

热点推荐