Description

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。例如，序列Z=<B,C,D,B>是序列X=<A,B,C,D,A,B>的子序列；

       给定两个序列X和Y，当另一个序列Z既是X的子序列又是Y的子序列时，称Z是序列X，Y的公共子序列。

例如：若X=<A,B,C,B,D,A,B>,Y=<B,D,C,A,B,A>,那么：<B,C,A>是X和Y的一个公共子序列，<B,C,B,A>也是X和Y的一个公共子序列；

       编程求出给定的两个序列中，最长公共子序列的长度。

Input Format

共两行，各一个字符串，第一个字符串表示第一个序列，第二个字符串表示第二个序列，两个字符串长度均小于1000 。

Output Format

一个整数，即两个序列的公共子序列的长度。

aabaaecd
ac

2

Source