记录编号	23350	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]最长公共子序列	最终得分	100
用户昵称	donny	是否通过	通过
代码语言	C++	运行时间	1.973 s
提交时间	2011-03-08 13:31:10	内存使用	0.26 MiB

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

timeval sstime, etime;

int main()
{
	ifstream fin("lcs.in");
	ofstream fout("lcs.out");

	string a,b;
	int x,y;
	int o,p;
	int f[2][5001];
	int g[2][5001];
	
	fin>>a;
	fin>>b;


	x=a.length()-1;
	y=b.length()-1;
	
	for (int i=0;i<=y;i++)
	{
		f[0][i]=0;
		g[0][i]=1;
	}
	g[1][0]=1;
	f[1][0]=0;
	
	
	p=0;
	for (int i=1;i<=x;i++)
	{
		o=p;
		p=(p==0)?1:0;
		
		f[p][0]=0;
		g[p][0]=1;
		
		for (int j=1;j<=y;j++)
		{
			if (a[i-1]!=b[j-1])
			{
				if (f[p][j-1]==f[o][j])
				{
					f[p][j]=f[o][j];
					g[p][j]=g[o][j]+g[p][j-1];
					if (f[o][j-1]==f[o][j])	
						g[p][j]=g[p][j]-g[o][j-1];
				}
				else
				{
					if (f[p][j-1]>f[o][j])
					{
						g[p][j]=g[p][j-1];
						f[p][j]=f[p][j-1];
					}
					else
					{
						g[p][j]=g[o][j];
						f[p][j]=f[o][j];
					}
				}
			}
			else
			{
				f[p][j]=f[o][j-1]+1;
				g[p][j]=g[o][j-1];
				if (f[o][j]==f[p][j])
					g[p][j]=g[p][j]+g[o][j];
				if (f[p][j-1]==f[p][j])
					g[p][j]=g[p][j]+g[p][j-1];
			}
			
			g[p][j]=g[p][j] % 100000000;
		}
		
	}
	
	
	fout<<f[x % 2][y]<<endl<<g[x % 2][y]<<endl;
	
	fin.close();
	fout.close();
	
	return 0;
}