题目名称	445. [HAOI 2010]最长公共子序列
输入输出	`lcs.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	徐明昭于2010-04-26加入修改该题
开放分组	全部用户
提交状态
分类标签	HAOI 动态规划字符串
	分享题解

通过：191，提交：554，通过率：34.48%
Hzoi_chairman	100	0.518 s	0.20 MiB	C++
李帅超	100	0.524 s	0.40 MiB	C++
xz康	100	0.546 s	0.20 MiB	C++
郭森宇	100	0.589 s	0.39 MiB	C++
龚林源	100	0.594 s	0.38 MiB	C++
hzoi	100	0.627 s	0.37 MiB	C++
野	100	0.640 s	0.16 MiB	C++
刘睿佳	100	0.660 s	0.40 MiB	C++
吴华骏	100	0.665 s	0.38 MiB	C++
sxysxy	100	0.674 s	2.28 MiB	C++

关于最长公共子序列的近10条评论(全部评论)
AntiLeaf 2017-05-25 15:47 15楼
。 Zwoi_只会打表抄代码的蒟蒻 2016-11-06 21:24 14楼
bzoj能过这里被卡常卡到80....毒瘤. sxysxy 2016-10-23 10:39 13楼
Respawn 2016-04-09 20:01 12楼
. NewBee 2016-04-02 07:41 11楼
LOSER 2016-04-01 10:47 10楼
回复 @=_= : 233333，之前初始化不是0，后来忘删了 liu_runda 2016-04-01 10:07 9楼
回复 @liu_runda : 达哥，，你的预处理好像没有什么意义吧 Sky_miner 2016-03-26 10:27 8楼
哒哒哒哒哒！ 2016-03-26 10:19 7楼
啦啦啦 ‎MistyEye 2016-03-26 10:15 6楼

445. [HAOI 2010]最长公共子序列

★★ 输入文件：lcs.in 输出文件：lcs.out 简单对比
时间限制：1 s 内存限制：256 MiB

【问题描述】

字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列 $x = "x_0，x_1，…，x_{n-1}"$，序列 $Y="y_0，y_1，…，y_{k-1}"$ 是 $X$ 的子序列，存在 $X$ 的一个严格递增下标序列，例如，$x="ABCBDAB"$，$Y="BCDB"$ 是 $X$ 的一个子序列。

对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。

【输入格式】

第 $1$ 行为第 $1$ 个字符序列，都是大写字母组成，以"$.$"结束，长度小于 $5000$。

第 $2$ 行为第 $2$ 个字符序列，都是大写字母组成，以"$.$"结束，长度小于 $5000$。

【输出格式】

第 $1$ 行输出上述两个最长公共子序列的长度。

第 $2$ 行输出所有可能出现的最长公共子序列个数，答案可能很大，只要将答案对 $100,000,000$ 求余即可。

【输入样例】

ABCBDAB.
BACBBD.

【输出样例】

4
7