[C語言]請幫我改一題程式~最長共同子序列

Question

題目:

http://www.fg.tp.edu.tw/~janet/cmptest/program/p91.htm

我的CODE:


#include
#include
#include

int lcs(char *, char *);
void output(char *, int , int);
int prev[100][100] = {0};
int lenth[100][100];

int main()
{
char str1[100], str2[100];
int m, n;
int len;
int i, j;
int k, p;

scanf("%d", &m);
for(k = 1; k <= m; k++)
scanf("%c", &str1[k]);

scanf("%d", &n);
for(p = 1; p <= n; p++)
scanf("%c", &str2[p]);

len = lcs(str1, str2);
printf("%d\n", len);

output(str1, m, n);

system("PAUSE");
return 0 ;
}

int lcs(char *x, char *y)
{
int i, j;
int m, n;
m = strlen(x);
n = strlen(y);

for (i = 0; i <= m; i++)
lenth[i][0] = 0;
for (j = 1; j <= n; j++)
lenth[0][j] = 0;

lenth[0][0] = 0;

for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
{
if (x[i - 1] == y[j - 1])
{
lenth[i][j] = lenth[i - 1][j - 1] + 1;
prev[i][j] = 1;
}

else
{
if (lenth[i][j - 1] >= lenth[i - 1][j])
{
prev[i][j] = 2;
lenth[i][j] = lenth[i][j - 1];
}

else
{
prev[i][j] = 3;
lenth[i][j] = lenth[i - 1][j];
}
}
}
return lenth[m][n];
}

void output(char *x, int i, int j)
{
if (i == 0 && j == 0) return;
if (prev[i][j] == 1)
{
output(x, i - 1, j - 1);
printf("%c", x[i - 1]);
}
else if (prev[i][j] == 2)
output(x, i, j - 1);
else if (prev[i][j] == 3)
output(x, i - 1, j);
}

Answer 1

原程式修改方式如下:

int main()
{
char str1[101], str2[101]; //增加一個位置放\0
int m, n;
int len;
int i, j; //此行可去掉
int k, p;

scanf("%d\n", &m); //說明如下:
//scanf內必須加入\n, 用以將'\n'去掉, 否則'\n'會留在輸入緩衝內,
//以致後續的for迴圈無法正確讀入所要的m個字元

for(k = 0; k < m; k++) { //k的範圍應為0~m
scanf("%c", &str1[k]);
}
str1[k]=0; //字串結尾應為0

scanf("%d\n", &n); //理由同 scanf("%d\n", &m);
for(p = 0; p < n; p++) { //p的範圍應為0~n
scanf("%c", &str2[p]);
}
str2[p]=0; //理由同 str1[k]=0;

//以下沒動

len = lcs(str1, str2);
printf("%d\n", len);

output(str1, m, n);

system("PAUSE");
return 0 ;
}

Answer 2

我是用配置記憶體來記錄字串
//Power by Visual Studio 2005
#include
#include
#include
char *subsequence(char *buffer, char *Sequence1, char *Sequence2){
int short_num,long_num,temp1,temp2,i,j=0,force=0;
for(temp1=0;Sequence1[temp1]!='\0';temp1++);
for(temp2=0;Sequence2[temp2]!='\0';temp2++);
short_num=(temp1<=temp2)?temp1:temp2,long_num=(temp1>temp2)?temp1:temp2;
for(i=0;i if(temp1==short_num){
force=(int)(strchr(Sequence2+force,Sequence1[i])-Sequence2);
if(force>=0){
buffer[j++]=Sequence1[i],force++;
}else{
force=(i>0?force:0);
}
}else if(temp1==long_num){
force=(int)(strchr(Sequence1+force,Sequence2[i])-Sequence1);
if(force>=0){
buffer[j++]=Sequence2[i],force++;
}else{
force=(i>0?force:0);
}
}
}
buffer[j]='\0';
return buffer;
}
int main(int argc, char* argv[]){
//==========START==========//
int len_alpha,len_beta,len_buffer;
char *alpha,*beta,*buffer;
printf("Input length of Alpha= "),scanf("%d",&len_alpha);
alpha=(char*)malloc((len_alpha+1)*sizeof(char));
printf("Input Alpha string= "),scanf("%s",alpha),*(alpha+len_alpha)='\0';
printf("Input length of Beta= "),scanf("%d",&len_beta);
beta=(char*)malloc((len_beta+1)*sizeof(char));
printf("Input Beta string= "),scanf("%s",beta),*(beta+len_beta)='\0';
len_buffer=(len_alpha<=len_beta)?len_alpha:len_beta;
buffer=(char*)malloc((len_buffer+1)*sizeof(char));
printf("\nsub sequence= %s\n",subsequence(buffer,alpha,beta));
free(alpha),free(beta),free(buffer);
//==========END==========//
printf("\n"),system("PAUSE");
return 0;
}


2007-07-14 22:59:50 補充：
雖然程式碼很複雜，但是程式碼有經過數次除錯，執行起來絕對不會出現錯誤。