题目描述
字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个严格递增下标序列i0,i1,…,ik-1,使得对所有的j=0,1,…,k-1,有xij=yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。一个序列如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则称为已知序列的最长公共子序列。
给定两个字符序列,求这两个序列的最长公共子序列的长度。
输入描述
输入两行,分别为两个字符序列(长度不超过100)。
输出描述
输出一行,包含一个整数,表示 两个字符序列的最长公共子序列的长度。
样例输入
wwwcodepkucom
ipkuaboutyou
样例输出
4
提示
中最长公共子序列为pkuo,长度为4。