lcstest.c

来自「一个关于数据聚类和模式识别的程序,在生物化学,化学中因该都可以用到.希望对大家有」· C语言 代码 · 共 68 行

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void lcs(char *a, char *b, char *result) {
	int **table, **previ, **prevj;
	int m = strlen(a), n = strlen(b);
	int count, i, j;

	/* Memory allocation */
	table = (int **) malloc(sizeof(int)*(m+1));
	table[0] = (int *) malloc(sizeof(int)*(m+1)*(n+1));
	for (i=1; i<=m; i++)
		table[i] = table[i-1]+n+1;

	/* Set initial conditions for dynamic programming table */
	for (i=0; i<=m; table[i][0]=0, i++);
	for (j=0; j<=n; table[0][j]=0, j++);

	/* Dynamic programming */
	for (i=1; i<=m; i++)
		for (j=1; j<=n; j++)
			if (a[i-1]==b[j-1])
				table[i][j] = table[i-1][j-1]+1;
			else if (table[i][j-1] > table[i-1][j])
				table[i][j] = table[i][j-1];
			else
				table[i][j] = table[i-1][j];

	/* Print the DP table */
	/*
	for (i=0; i<=m; i++) {
		for (j=0; j<=n; j++)
			printf("%d ", table[i][j]);
		printf("\n");
	}
	*/

	/* Put the result */
	result[table[m][n]] = '\0';
	count = table[m][n];
	for (i=m, j=n; (i!=0)&&(j!=0); ) {
		if (table[i][j] == table[i-1][j])
			i--;
		else if (table[i][j] == table[i][j-1])
			j--;
		else {
			result[--count] = a[i-1];
			i--; j--;
		}
	}

	/* Free memory */
	free(table[0]); free(table);
}

main() {
	char a[]      = "This is tests A B C";
	char b[]      = "More test B";
	char result[] = "                 ";

	printf("String 1 = \"%s\"\n", a);
	printf("String 2 = \"%s\"\n", b);
	lcs(a, b, result);
	printf("LCS = \"%s\"\n", result);
	printf("LCS length = %d\n", strlen(result));
}