记录编号	240256	评测结果	AAAAAAAAAA
题目名称	最长公共子序列	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.540 s
提交时间	2016-03-22 14:48:24	内存使用	95.88 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 5005; 
int f[maxn][maxn];
char a[maxn], b[maxn];
int cnta, cntb;
void read() {
	char tmp;
	tmp = getchar();
	cnta = 0;
	while(tmp < 'A' || tmp > 'Z') tmp = getchar();
	while(tmp != '.') {
		a[++cnta] = tmp;
		tmp = getchar();
	}
	cntb = 0;
	while(tmp < 'A' || tmp > 'Z') tmp = getchar();
	while(tmp != '.') {
		b[++cntb] = tmp;
		tmp = getchar();
	}
}
void solve() {
	for(int i = 1; i <= cnta; i++) {
		for(int j = 1; j <= cntb; j++) {
			if(a[i] == b[j]) f[i][j] = f[i-1][j-1]+1;//如果当前位相同，那对应的子序列相同数+1 
			else f[i][j] = max(f[i][j-1], f[i-1][j]);
		}
	} 
	printf("%d\n", f[cnta][cntb]);
}
int main() {
	freopen("lcslength.in", "r", stdin);
	freopen("lcslength.out", "w", stdout); 
	read();
	solve();
	return 0;
}