记录编号	324440	评测结果	AAAAAAAAAA
题目名称	最长公共子序列	最终得分	100
用户昵称	Janis	是否通过	通过
代码语言	C++	运行时间	1.138 s
提交时间	2016-10-18 08:55:17	内存使用	96.07 MiB

/*
状态定义：dp[i][j]表示序列A从1~i，序列B从1~j的最长公共子序列长度
转移方程：if(a[i]=b[j])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max{dp[i-1][j],dp[i][j-1]}
边界：dp[0][0]=0;dp[lenA][lenB]为答案
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 5010;
char a[maxn],b[maxn];
int dp[maxn][maxn];

void Init(){
	scanf("%s%s",a+1,b+1);
	int lena = strlen(a+1), lenb = strlen(b+1);
	for(int i = 1; i <= lena; i++){
		for(int j = 1; j <= lenb; j++){
		//	if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1;
			dp[i][j] = max((a[i] == b[j] ? dp[i-1][j-1] + 1 : 0),max(dp[i-1][j],dp[i][j-1]));
		}
	}
	printf("%d",dp[lena][lenb]-1);
}
int main()
{
	#ifndef DEBUG
		string FileName="lcslength";
		freopen((FileName+".in").c_str(),"r",stdin);
		freopen((FileName+".out").c_str(),"w",stdout);
	#endif
	Init();
}