Two product catalogs each encode their item ordering as a string of lowercase letters. To measure how aligned the two orderings are, compute the length of their longest common subsequence: the greatest number of characters that appear in both strings in the same relative order (not necessarily contiguously).
Input format
Line 1: the first catalog string a.
Line 2: the second catalog string b.
Output format
A single integer: the length of the longest common subsequence of a and b.
Constraints
- 1 <= length of
a<= 40 - 1 <= length of
b<= 40 - Both strings consist of lowercase English letters only.