Longest Common Subsequence

Given two strings, determine the length of their Longest Common Subsequence (LCS). The LCS is defined as the longest sequence which can be derived from both strings by deleting some (or no) characters without changing the order of the remaining characters.

Your task is to implement an efficient algorithm to compute the LCS length. For example, given the strings "abcde" and "ace", the LCS is "ace" with a length of 3.

inputFormat

The input consists of two lines. The first line contains the first string, and the second line contains the second string.

outputFormat

Output a single integer representing the length of the longest common subsequence of the two input strings.## sample

abcde
ace

3