#P2516. [HAOI2010] 最长公共子序列

[HAOI2010] 最长公共子序列

题目描述

字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X={x0,x1,,xm1}X=\{x_0,x_1,\cdots ,x_{m-1}\},序列Y={y0,y1,,yk1}Y=\{y_0,y_1,\cdots ,y_{k-1}\}XX 的子序列,存在 XX 的一个严格递增下标序列 {i0,i1,,ik1}\{i_0,i_1,\cdots,i_{k-1}\} ,使得对所有的j=0,1,,k1j=0,1,\cdots,k-1 ,有 xij=yjx_{ij}=y_j 。例如,X="ABCBDAB"X=\verb!"ABCBDAB"!Y="BCDB"Y=\verb!"BCDB"!XX 的一个子序列。对给定的两个字符序列,求出他们最长的公共子序列长度,以及最长公共子序列个数。

输入格式

第一行为第一个字符序列,都是大写字母组成,以 . 结束,大写字母个数不超过 50005000

第二行为第二个字符序列,都是大写字母组成,以 . 结束,大写字母个数不超过 50005000

输出格式

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

第二行输出所有可能出现的最长公共子序列个数,答案可能很大,只要将答案对 10810^{8} 求余即可。

ABCBDAB.
BACBBD.
4
7