longestcommonseq.c

最长公共序列的C源码

#include "comm.h"

#define FIRST_CHAR 'A'
#define LAST_CHAR 'C'

#define CHAR_NUM 6

void initString(char* s,int num);
void printString(char* s,int num,char* info);
void LCS(char* s1,int L1,char* s2,int L2);

int main(void)
{
	char *s1,*s2;
	int L1,L2;
	srand((unsigned)time(NULL));
	
	L1=rand()%(CHAR_NUM/2)+1+CHAR_NUM/2;
	s1=(char*)calloc(L1,sizeof(char));
	initString(s1,L1);
	printString(s1,L1,"One string is:\n");
	
	L2=rand()%(CHAR_NUM/2)+1+CHAR_NUM/2;
	s2=(char*)calloc(L2,sizeof(char));
	initString(s2,L2);
	printString(s2,L2,"The other string is:\n");
	
	LCS(s1,L1,s2,L2);
	
	free(s1);
	free(s2);
	return 0;
}


void initString(char* s,int num)
{
	int i=0;
	for(i=0;i<num;i++){
		s[i]=rand()%(LAST_CHAR-FIRST_CHAR+1)+FIRST_CHAR;
	}
}

void printString(char* s,int num,char* info)
{
	int i=0;
	printf(info);
	for(i=0;i<num;i++){
		printf("%3c",s[i]);
	}
	putchar('\n');
}

void LCS(char* s1,int L1,char* s2,int L2)
{
	int i=0,j=0,k=0,m=0;
	int table[CHAR_NUM+1][CHAR_NUM+1];
	char lcs[CHAR_NUM];
	for(i=0;i<=L1;i++){
		table[i][0]=0;
	}
	for(i=0;i<=L2;i++){
		table[0][i]=0;
	}
	for(i=1;i<=L1;i++){
		for(j=1;j<=L2;j++){
			if(s1[i-1]==s2[j-1])
				table[i][j]=table[i-1][j-1]+1;
			else
				table[i][j]=table[i][j-1] > table[i-1][j] ? table[i][j-1] : table[i-1][j];
		}
	}
	
	printf("\nDecision table is:\n");
	for(i=0;i<=L1;i++){
		for(j=0;j<=L2;j++){
			printf("%3d",table[i][j]);
		}
		putchar('\n');
	}

	m=L2;
	for(i=L1;i>0;i--){
		for(j=m;j>0;j--){
			if(table[i][j]==table[i-1][j]){ //上行
				m=j;
				break;
			}
			else if(table[i][j]==table[i][j-1]){ //左行
				continue;
			}
			else{ //左上行
				lcs[k++]=s2[j-1];
				m=j-1;
				break;
			}
			
		}
	}

	printf("\nLongest common sequence is:\n");
	for(i=k-1;i>=0;i--){
		printf("%3c",lcs[i]);
	}

}