题目描述

一天，爷爷给了小可可一个密码盒，盒子上有两行字符串：

爷爷告诉小可可，打开盒子的密码就是这两行字符串的最长公共子序列的长度。

小可可上网找到关于最长公共子序列的定义，描述如下：

一个给定序列的某个子序列即给定的序列再去掉几个元素（可能一个也不去掉），也就是给定一序列 $X=<x_1,x_2,\dots,x_m>$，另一序列 $Z=<z_1,z_2,\dots,z_k>$ 是 $X$ 的子序列，如果存在 $X$ 的一个严格递增下标序列 $<i_1,i_2,\dots,i_k>$ 使得对所有的 $j=1,2,\dots,k$ 有 $x_{i_j}=z_j$。例如， $z=<B,C,D,B>$ 就是 $X=<A,B,C,B,D,A,B>$ 的一个子序列，相应的下标序列为 $<2,3,5,7>$。其中，$A$，$B$，$C$，$D$ 均为字符 $0$ 或者 $1$。

例如：当 $X=<1,1,1,0>,Y=<1,0,0,0,0,1,0,0,0>$ 时，最长公共子序列为 $110$，其长度为 $3$；当 $X=<1,0,1,0,0,0,1>,Y=<0,0,0,0,1,1,1>$ 时，最长公共子序列为 $00001$，其长度为 $5$。

请你帮小可可编写程序找到开锁密码。（注意：尽量降低程序的时间复杂度）

输入格式

输入文件中包含两个字符串 $X$ 和 $Y$。当中两字符串非 $0$ 即 $1$。序列长度均小于 $9999$。

输出格式

$X$ 和 $Y$ 的最长公共子序列长度。

01010101010 00000011111

6

01011 010010101111111111

5