记录编号	112815	评测结果	AAAAAAAAAA
题目名称	最长公共子序列	最终得分	100
用户昵称	RACHE	是否通过	通过
代码语言	C++	运行时间	0.548 s
提交时间	2014-07-17 10:05:12	内存使用	99.54 MiB

#include<iostream>
#include<cstdio>
#include<fstream>
#include<string>
#include<algorithm>
using namespace std;
int m=0,n=0;
int i,j;
ifstream fin("lcslength.in");
ofstream fout("lcslength.out");
string s1,s2;
int sum=0,p=0,k,x=1;
int r2[5100][5100]={0};
char c[5100],d[5100];
/*void out(int s[5000][5000],string x,int m,int k)
{
	if(m==0||k==0)
		return;
	if(s[m][k]==0)
	{
		out(s,x,m-1,k-1);
	}
	else if(s[m][k]==1)
	{
		out(s,x,m-1,k);
		sum++;
	}
	else
	{
		out(s,x,m,k-1);
	}
}*/
int main()
{
	fin>>s1>>s2;
	m=s1.length();
	n=s2.length();
	while(s1[p]!='.')
	{
		c[x]=s1[p];
		x++;
		p++;
	}
	p=0;
	x=1;
	while(s2[p]!='.')
	{
		d[x]=s2[p];
		x++;
		p++;
	}
	for(i=1;i<m;i++)
	{
		r2[i][0]=0;
	}
	for(j=0;j<n;j++)
	{
		r2[0][j]=0;
	}
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(c[i]==d[j])
			{
				r2[i][j]=r2[i-1][j-1]+1;
			}
			else
			{
				r2[i][j]=max(r2[i][j-1],r2[i-1][j]);
			}
		}
	}
	fout<<r2[m][n]-1;
	return 0;
}