记录编号	57738	评测结果	AAAAAAAAAA
题目名称	最长公共子序列	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.489 s
提交时间	2013-04-12 14:43:57	内存使用	95.76 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int SIZEN=5001;
int s1[SIZEN]={0},s2[SIZEN]={0};
int l1,l2;
int f[SIZEN][SIZEN]={0};
void read(void){
	string str;
	int i;
	cin>>str;
	i=0;
	while(str[i]!='.') s1[i+1]=str[i]-'A',i++;
	l1=i;
	cin>>str;
	i=0;
	while(str[i]!='.') s2[i+1]=str[i]-'A',i++;
	l2=i;
}
void dp(void){
	int i,j;
	for(i=1;i<=l1;i++){
		for(j=1;j<=l2;j++){
			if(s1[i]==s2[j]) f[i][j]=f[i-1][j-1]+1;
			else f[i][j]=max(f[i][j-1],f[i-1][j]);
		}
	}
}
int main(){
	freopen("lcslength.in","r",stdin);
	freopen("lcslength.out","w",stdout);
	read();
	dp();
	printf("%d\n",f[l1][l2]);
	return 0;
}