dynamic_layout_method.cpp

数据结构里的动态规化法

#include <stdio.h>
#include <string.h>
#define N 100
char a[N],b[N],str[N];
int lcs_len(char *a,char *b,int c[][N]){
	int m=strlen(a), n=strlen(b), i, j;
	for(i=0;i<=m;i++) c[i][0]=0;//column 0 is 0
	for(j=0;j<=n;j++) c[0][j]=0;//line 0 is 0
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			if(a[i-1]==b[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];
	return c[m][n];
}

char *build_lcs(char s[],char *a, char *b){
	int k, i=strlen(a), j=strlen(b), c[N][N];
	k=lcs_len(a,b,c);
	s[k]='\0';
	while(k>0)
		if(c[i][j]==c[i-1][j]) i--;
		else if(c[i][j]==c[i][j-1]) j--;
		else{
			s[--k]=a[i-1];
			i--;
			j--;
		}
	return s;
}

void main(){
	printf("Enter two string(<%d)!\n",N);
	scanf("%s %s",a,b);
	printf("LCS=%s\n",build_lcs(str,a,b));
	printf("str=%s\n",str);
}