题目描述

给定序列$X = < x_1, x_2, ..., x_m >$的子序列是指从$X$中删除若干元素（可以不删除）后得到的序列。对于另一个序列$Z = < z_1, z_2, ..., z_k >$，如果存在一个严格递增的下标序列$< i_1, i_2, ..., i_k >$，使得对于所有$j = 1,2,...,k$，都有$x_{i_j} = z_j$，那么$Z$就是$X$的子序列。例如，$Z = < a, b, f, c >$是$X = < a, b, c, f, b, c >$的子序列，对应的下标序列为$< 1, 2, 4, 6 >$。给定两个序列$X$和$Y$，问题是找出$X$和$Y$的最长公共子序列的长度。

输入格式

程序输入来自标准输入。输入中的每个数据集包含两个字符串，表示给定的序列。序列之间由任意数量的空白字符分隔。输入数据保证正确。

输出格式

对于每组数据，程序在标准输出的单独一行开头打印最长公共子序列的长度。

输入样例1

abcfbc         abfcab
programming    contest 
abcd           mnp

输出样例1

4
2
0

来源

2003年东南欧地区