A subsequence of a string is obtained by deleting zero or more characters without changing the order of the remaining ones. Given two strings s and t, find the length of the longest string that is a subsequence of both.
Input format
Line 1: the string s (possibly empty).
Line 2: the string t (possibly empty).
Both strings contain only lowercase letters a-z.
Output format
A single integer: the length of the longest common subsequence (0 if there is none).
Constraints
- 0 <= length of each string <= 1000