记录编号	216818	评测结果	AAAAAAAAAA
题目名称	最长公共子序列	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.282 s
提交时间	2015-12-31 14:12:18	内存使用	0.30 MiB

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SHARP ('.')
#define MAXL (5005)
#define AC_max(x,y) (x<y?y:x)

typedef struct TAG_ANSI_STRING
{
	char *buffer;
	int length;
}ANSI_STRING, *PANSI_STRING;

void fast_read(PANSI_STRING str)
{
	char c;
	while((c = getchar()) && c != '.') 
		str -> buffer[str -> length ++] = c;
}

void init_string(PANSI_STRING str, int reserve_len)
{
	str -> buffer = (char *)malloc(reserve_len);
	str -> length = 0;
}

void des_string(PANSI_STRING str)
{
	free(str -> buffer);
}

int dp[2][MAXL];
int lcs(PANSI_STRING stra, PANSI_STRING strb)
{
	int i,j;
	for(i = 1; i <= stra -> length; i++)
		for(j = 1; j <= strb -> length; j++)
			if(stra -> buffer[i-1] == strb -> buffer[j-1])
				dp[i&1][j] = dp[!(i&1)][j-1] + 1;
			else
				dp[i&1][j] = AC_max(dp[!(i&1)][j], dp[i&1][j-1]);
	return dp[stra -> length & 1][j-1];
}

void set_file()
{
	freopen("lcslength.in", "r", stdin);
	freopen("lcslength.out", "w", stdout);		
}

int main()
{
	set_file();	
	ANSI_STRING stra;
	ANSI_STRING strb;
	init_string(&stra, MAXL);
	init_string(&strb, MAXL);
	 
	fast_read(&stra);
	fast_read(&strb);
	
	printf("%d\n", lcs(&stra, &strb));
	
	des_string(&stra);
	des_string(&strb);
	return 0;
}